--- a/mobile/android/base/GcmAndroidManifest_services.xml.in
+++ b/mobile/android/base/GcmAndroidManifest_services.xml.in
@@ -2,16 +2,23 @@
         <service
             android:name="org.mozilla.gecko.gcm.GcmInstanceIDListenerService"
             android:exported="false">
             <intent-filter>
                 <action android:name="com.google.android.gms.iid.InstanceID"/>
             </intent-filter>
         </service>
 
+        <!-- Handle token refresh in background - https://developers.google.com/cloud-messaging/android/client -->
+        <service
+            android:name="org.mozilla.gecko.gcm.GcmTokenRefreshService"
+            android:permission="android.permission.BIND_JOB_SERVICE"
+            android:exported="false">
+        </service>
+
         <!-- Provided by on-device Google Play Services.  Directs inbound messages to internal listener service. -->
         <receiver
             android:name="com.google.android.gms.gcm.GcmReceiver"
             android:exported="true"
             android:permission="com.google.android.c2dm.permission.SEND">
             <intent-filter>
                 <action android:name="com.google.android.c2dm.intent.RECEIVE" />
                 <action android:name="com.google.android.c2dm.intent.REGISTRATION" />

--- a/mobile/android/base/java/org/mozilla/gecko/JobIdsConstants.java
+++ b/mobile/android/base/java/org/mozilla/gecko/JobIdsConstants.java
@@ -42,16 +42,18 @@ public class JobIdsConstants {
     private static final int JOB_ID_UPDATES_APPLY = 1012;
 
     private static final int JOB_ID_CRASH_REPORTER = 1013;
 
     private static final int JOB_ID_GECKO_STARTER = 1014;
     private static final int JOB_ID_GECKO_LIBS_LOADER = 1015;
     private static final int JOB_ID_GECKO_SERVICES_CREATOR = 1016;
 
+    private static final int JOB_ID_GCM_TOKEN_REFRESH = 1017;
+
     public static int getIdForDlcStudyJob() {
         return getIdWithOffset(JOB_ID_DLC_STUDY);
     }
 
     public static int getIdForDlcDownloadJob() {
         return getIdWithOffset(JOB_ID_DLC_DOWNLOAD);
     }
 
@@ -110,16 +112,20 @@ public class JobIdsConstants {
     public static int getIdForGeckoLibsLoader() {
         return getIdWithOffset(JOB_ID_GECKO_LIBS_LOADER);
     }
 
     public static int getIdForGeckoServicesCreator() {
         return getIdWithOffset(JOB_ID_GECKO_SERVICES_CREATOR);
     }
 
+    public static int getIdForGcmTokenRefresher() {
+        return getIdWithOffset(JOB_ID_GCM_TOKEN_REFRESH);
+    }
+
     private static boolean isReleaseBuild() {
         return AppConstants.RELEASE_OR_BETA;
     }
 
     private static int getIdWithOffset(final int jobIdUsedInRelease) {
         return isReleaseBuild() ? jobIdUsedInRelease : jobIdUsedInRelease + BETA_OFFSET;
     }
 }

--- a/mobile/android/base/java/org/mozilla/gecko/gcm/GcmInstanceIDListenerService.java
+++ b/mobile/android/base/java/org/mozilla/gecko/gcm/GcmInstanceIDListenerService.java
@@ -4,32 +4,25 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 package org.mozilla.gecko.gcm;
 
 import android.util.Log;
 
 import com.google.android.gms.iid.InstanceIDListenerService;
 
-import org.mozilla.gecko.push.PushService;
-import org.mozilla.gecko.util.ThreadUtils;
-
 /**
  * This service is notified by the on-device Google Play Services library if an
  * in-use token needs to be updated.  We simply pass through to AndroidPushService.
  */
 public class GcmInstanceIDListenerService extends InstanceIDListenerService {
     /**
      * Called if InstanceID token is updated. This may occur if the security of
      * the previous token had been compromised. This call is initiated by the
      * InstanceID provider.
      */
     @Override
     public void onTokenRefresh() {
-        Log.d("GeckoPushGCM", "Token refresh request received.  Processing on background thread.");
-        ThreadUtils.postToBackgroundThread(new Runnable() {
-            @Override
-            public void run() {
-                PushService.getInstance(GcmInstanceIDListenerService.this).onRefresh();
-            }
-        });
+        Log.d("GeckoPushGCM", "Token refresh request received");
+
+        GcmTokenRefreshService.enqueueWork(this);
     }
 }

new file mode 100644
--- /dev/null
+++ b/mobile/android/base/java/org/mozilla/gecko/gcm/GcmTokenRefreshService.java
@@ -0,0 +1,38 @@
+/* -*- Mode: Java; c-basic-offset: 4; tab-width: 4; indent-tabs-mode: nil; -*-
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+package org.mozilla.gecko.gcm;
+
+import android.content.Context;
+import android.content.Intent;
+import android.support.annotation.NonNull;
+import android.support.v4.app.JobIntentService;
+import android.util.Log;
+
+import org.mozilla.gecko.JobIdsConstants;
+import org.mozilla.gecko.push.PushService;
+
+/**
+ * As per <a href="https://developers.google.com/cloud-messaging/android/client">
+ *     Google recommendations for setting a GCM Client</a>
+ * we should use a JobIntentService to handle the token refresh.
+ */
+public class GcmTokenRefreshService extends JobIntentService {
+    private static final String LOGTAG = "GeckoPushGCM";
+    private static final boolean DEBUG = false;
+
+    @Override
+    protected void onHandleWork(@NonNull Intent intent) {
+        if (DEBUG) {
+            Log.d(LOGTAG, "Processing token refresh on in background");
+        }
+
+        PushService.getInstance(this).onRefresh();
+    }
+
+    public static void enqueueWork(@NonNull final Context context) {
+        enqueueWork(context, GcmTokenRefreshService.class, JobIdsConstants.getIdForGcmTokenRefresher(), new Intent());
+    }
+}