--- a/mobile/android/base/AndroidManifest.xml.in
+++ b/mobile/android/base/AndroidManifest.xml.in
@@ -450,16 +450,17 @@
                 <action android:name="android.support.customtabs.action.CustomTabsService" />
             </intent-filter>
         </service>
 
 #include ../services/manifests/FxAccountAndroidManifest_services.xml.in
 
         <service
             android:name="org.mozilla.gecko.tabqueue.TabReceivedService"
+            android:permission="android.permission.BIND_JOB_SERVICE"
             android:exported="false" />
 
 
 #ifdef MOZ_ANDROID_MLS_STUMBLER
 #include ../stumbler/manifests/StumblerManifest_services.xml.in
 #endif
 
 #ifdef MOZ_ANDROID_GCM

--- a/mobile/android/base/java/org/mozilla/gecko/JobIdsConstants.java
+++ b/mobile/android/base/java/org/mozilla/gecko/JobIdsConstants.java
@@ -22,32 +22,38 @@ public class JobIdsConstants {
     // Offset to differentiate the ids for Release/Beta versions of the app
     private static final int BETA_OFFSET = 1000;
 
     private static final int JOB_ID_DLC_STUDY = 1000;
     private static final int JOB_ID_DLC_DOWNLOAD = 1001;
     private static final int JOB_ID_DLC_SYNCHRONIZE = 1002;
     private static final int JOB_ID_DLC_CLEANUP = 1003;
 
+    private static final int JOB_ID_TAB_RECEIVED = 1004;
+
     public static int getIdForDlcStudyJob() {
         return getIdWithOffset(JOB_ID_DLC_STUDY);
     }
 
     public static int getIdForDlcDownloadJob() {
         return getIdWithOffset(JOB_ID_DLC_DOWNLOAD);
     }
 
     public static int getIdForDlcSynchronizeJob() {
         return getIdWithOffset(JOB_ID_DLC_SYNCHRONIZE);
     }
 
     public static int getIdForDlcCleanupJob() {
         return getIdWithOffset(JOB_ID_DLC_CLEANUP);
     }
 
+    public static int getIdForTabReceivedJob() {
+        return getIdWithOffset(JOB_ID_TAB_RECEIVED);
+    }
+
     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/tabqueue/TabReceivedService.java
+++ b/mobile/android/base/java/org/mozilla/gecko/tabqueue/TabReceivedService.java
@@ -1,56 +1,52 @@
 /* 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.tabqueue;
 
-import org.mozilla.gecko.AppConstants;
-import org.mozilla.gecko.BrowserLocaleManager;
-import org.mozilla.gecko.GeckoSharedPrefs;
-import org.mozilla.gecko.R;
-import org.mozilla.gecko.db.BrowserContract;
-
-import android.app.IntentService;
 import android.app.PendingIntent;
 import android.content.Intent;
 import android.content.SharedPreferences;
 import android.content.res.Resources;
 import android.database.Cursor;
 import android.media.RingtoneManager;
 import android.net.Uri;
+import android.support.annotation.NonNull;
 import android.support.annotation.Nullable;
 import android.support.annotation.WorkerThread;
+import android.support.v4.app.JobIntentService;
 import android.support.v4.app.NotificationCompat;
 import android.support.v4.app.NotificationManagerCompat;
 import android.util.Log;
 
+import org.mozilla.gecko.AppConstants;
+import org.mozilla.gecko.BrowserLocaleManager;
+import org.mozilla.gecko.GeckoSharedPrefs;
+import org.mozilla.gecko.R;
+import org.mozilla.gecko.db.BrowserContract;
+
 /**
- * An IntentService that displays a notification for a tab sent to this device.
+ * A JobIntentService that displays a notification for a tab sent to this device.
  *
  * The expected Intent should contain:
  *   * Data: URI to open in the notification
  *   * EXTRA_TITLE: Page title of the URI to open
  */
-public class TabReceivedService extends IntentService {
+public class TabReceivedService extends JobIntentService {
     private static final String LOGTAG = "Gecko" + TabReceivedService.class.getSimpleName();
 
     private static final String PREF_NOTIFICATION_ID = "tab_received_notification_id";
 
     private static final int MAX_NOTIFICATION_COUNT = 1000;
 
-    public TabReceivedService() {
-        super(LOGTAG);
-        setIntentRedelivery(true);
-    }
-
     @Override
-    protected void onHandleIntent(final Intent intent) {
-        // IntentServices don't keep the process alive so
+    protected void onHandleWork(@NonNull Intent intent) {
+        // JobIntentServices doesn't keep the process alive so
         // we need to do this every time. Ideally, we wouldn't.
         final Resources res = getResources();
         BrowserLocaleManager.getInstance().correctLocale(this, res, res.getConfiguration());
 
         final String uri = intent.getDataString();
         if (uri == null) {
             Log.d(LOGTAG, "Received null uri – ignoring");
             return;
@@ -83,16 +79,22 @@ public class TabReceivedService extends 
 
         // Save the ID last so if the Service is killed and the Intent is redelivered,
         // the ID is unlikely to have been updated and we would re-use the the old one.
         // This would prevent two identical notifications from appearing if the
         // notification was shown during the previous Intent processing attempt.
         prefs.edit().putInt(PREF_NOTIFICATION_ID, notificationId).apply();
     }
 
+    @Override
+    public boolean onStopCurrentWork() {
+        // Reschedule the work if it has been stopped before completing (shouldn't)
+        return true;
+    }
+
     /**
      * @param clientGUID the guid of the client in the clients table
      * @return the client's name from the clients table, if possible, else the brand name.
      */
     @WorkerThread
     private String getNotificationTitle(@Nullable final String clientGUID) {
         if (clientGUID == null) {
             Log.w(LOGTAG, "Received null guid, using brand name.");

--- a/mobile/android/services/src/main/java/org/mozilla/gecko/sync/CommandProcessor.java
+++ b/mobile/android/services/src/main/java/org/mozilla/gecko/sync/CommandProcessor.java
@@ -4,21 +4,23 @@
 
 package org.mozilla.gecko.sync;
 
 import android.content.ComponentName;
 import android.content.Context;
 import android.content.Intent;
 import android.net.Uri;
 import android.support.annotation.Nullable;
+import android.support.v4.app.JobIntentService;
 import android.text.TextUtils;
 import android.util.Log;
 
 import org.json.simple.JSONArray;
 import org.json.simple.JSONObject;
+import org.mozilla.gecko.JobIdsConstants;
 import org.mozilla.gecko.background.common.log.Logger;
 import org.mozilla.gecko.db.BrowserContract;
 import org.mozilla.gecko.fxa.authenticator.AndroidFxAccount;
 import org.mozilla.gecko.sync.repositories.NullCursorException;
 import org.mozilla.gecko.sync.repositories.android.ClientsDatabaseAccessor;
 import org.mozilla.gecko.sync.repositories.domain.ClientRecord;
 import org.mozilla.gecko.sync.telemetry.TelemetryEventCollector;
 import org.mozilla.gecko.util.StringUtils;
@@ -306,15 +308,17 @@ public class CommandProcessor {
     }
 
     String title = null;
     if (args.size() == 3) {
       title = args.get(2);
     }
 
     final Intent sendTabNotificationIntent = new Intent();
-    sendTabNotificationIntent.setClassName(context, BrowserContract.TAB_RECEIVED_SERVICE_CLASS_NAME);
     sendTabNotificationIntent.setData(Uri.parse(uri));
     sendTabNotificationIntent.putExtra(Intent.EXTRA_TITLE, title);
     sendTabNotificationIntent.putExtra(BrowserContract.EXTRA_CLIENT_GUID, clientId);
-    final ComponentName componentName = context.startService(sendTabNotificationIntent);
+    final ComponentName componentName = new ComponentName(context, BrowserContract.TAB_RECEIVED_SERVICE_CLASS_NAME);
+    final int tabReceivedServiceJobId = JobIdsConstants.getIdForTabReceivedJob();
+
+    JobIntentService.enqueueWork(context, componentName, tabReceivedServiceJobId, sendTabNotificationIntent);
   }
 }