--- a/mobile/android/base/java/org/mozilla/gecko/JobIdsConstants.java
+++ b/mobile/android/base/java/org/mozilla/gecko/JobIdsConstants.java
@@ -25,16 +25,17 @@ public class JobIdsConstants {
     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;
 
     private static final int JOB_ID_PROFILE_FETCH = 1005;
+    private static final int JOB_ID_PROFILE_DELETE = 1006;
 
     public static int getIdForDlcStudyJob() {
         return getIdWithOffset(JOB_ID_DLC_STUDY);
     }
 
     public static int getIdForDlcDownloadJob() {
         return getIdWithOffset(JOB_ID_DLC_DOWNLOAD);
     }
@@ -50,16 +51,20 @@ public class JobIdsConstants {
     public static int getIdForTabReceivedJob() {
         return getIdWithOffset(JOB_ID_TAB_RECEIVED);
     }
 
     public static int getIdForProfileFetchJob() {
         return getIdWithOffset(JOB_ID_PROFILE_FETCH);
     }
 
+    public static int getIdForProfileDeleteJob() {
+        return getIdWithOffset(JOB_ID_PROFILE_DELETE);
+    }
+
     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/services/manifests/FxAccountAndroidManifest_services.xml.in
+++ b/mobile/android/services/manifests/FxAccountAndroidManifest_services.xml.in
@@ -7,17 +7,18 @@
 
             <meta-data
                 android:name="android.accounts.AccountAuthenticator"
                 android:resource="@xml/fxaccount_authenticator" />
         </service>
 
         <service
             android:exported="false"
-            android:name="org.mozilla.gecko.fxa.receivers.FxAccountDeletedService" >
+            android:name="org.mozilla.gecko.fxa.receivers.FxAccountDeletedService"
+            android:permission="android.permission.BIND_JOB_SERVICE" >
         </service>
 
         <service
             android:exported="false"
             android:name="org.mozilla.gecko.fxa.sync.FxAccountProfileService"
             android:permission="android.permission.BIND_JOB_SERVICE" >
         </service>
 

--- a/mobile/android/services/src/main/java/org/mozilla/gecko/fxa/authenticator/AndroidFxAccount.java
+++ b/mobile/android/services/src/main/java/org/mozilla/gecko/fxa/authenticator/AndroidFxAccount.java
@@ -811,22 +811,22 @@ public class AndroidFxAccount {
    *
    * @return local email address, obfuscated.
    */
   public String getObfuscatedEmail() {
     return Utils.obfuscateEmail(account.name);
   }
 
   /**
-   * Populate an intent used for starting FxAccountDeletedService service.
+   * Populate and return an intent used for starting FxAccountDeletedService service.
    *
-   * @param intent Intent to populate with necessary extras
    * @return <code>Intent</code> with a deleted action and account/OAuth information extras
    */
-  /* package-private */ Intent populateDeletedAccountIntent(final Intent intent) {
+  /* package-private */ Intent getIntentToDeleteAccount() {
+    final Intent intent = new Intent();
     final List<String> tokens = new ArrayList<>();
 
     intent.putExtra(FxAccountConstants.ACCOUNT_DELETED_INTENT_VERSION_KEY,
         Long.valueOf(FxAccountConstants.ACCOUNT_DELETED_INTENT_VERSION));
     intent.putExtra(FxAccountConstants.ACCOUNT_DELETED_INTENT_ACCOUNT_KEY, account.name);
     intent.putExtra(FxAccountConstants.ACCOUNT_DELETED_INTENT_ACCOUNT_PROFILE, getProfile());
 
     // Get the tokens from AccountManager. Note: currently, only reading list service supports OAuth. The following logic will

--- a/mobile/android/services/src/main/java/org/mozilla/gecko/fxa/authenticator/FxAccountAuthenticator.java
+++ b/mobile/android/services/src/main/java/org/mozilla/gecko/fxa/authenticator/FxAccountAuthenticator.java
@@ -361,22 +361,20 @@ public class FxAccountAuthenticator exte
     final AndroidFxAccount androidFxAccount = new AndroidFxAccount(context, account);
 
     // Deleting the pickle file in a blocking manner will avoid race conditions that might happen when
     // an account is unpickled while an FxAccount is being deleted.
     // Also we have an assumption that this method is always called from a background thread, so we delete
     // the pickle file directly without being afraid from a StrictMode violation.
     ThreadUtils.assertNotOnUiThread();
 
-    final Intent serviceIntent = androidFxAccount.populateDeletedAccountIntent(
-            new Intent(context, FxAccountDeletedService.class)
-    );
+    final Intent deleteProfileIntent = androidFxAccount.getIntentToDeleteAccount();
     Logger.info(LOG_TAG, "Account named " + account.name + " being removed; " +
-        "starting FxAccountDeletedService with action: " + serviceIntent.getAction() + ".");
-    context.startService(serviceIntent);
+        "starting FxAccountDeletedService with action: " + deleteProfileIntent.getAction() + ".");
+    FxAccountDeletedService.enqueueWork(context, deleteProfileIntent);
 
     Logger.info(LOG_TAG, "Firefox account named " + account.name + " being removed; " +
             "deleting saved pickle file '" + FxAccountConstants.ACCOUNT_PICKLE_FILENAME + "'.");
     deletePickle();
 
     return result;
   }
 

--- a/mobile/android/services/src/main/java/org/mozilla/gecko/fxa/receivers/FxAccountDeletedService.java
+++ b/mobile/android/services/src/main/java/org/mozilla/gecko/fxa/receivers/FxAccountDeletedService.java
@@ -1,31 +1,32 @@
 /* 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.fxa.receivers;
 
-import android.app.IntentService;
 import android.content.ContentResolver;
 import android.content.Context;
 import android.content.Intent;
 import android.net.Uri;
 import android.os.Bundle;
+import android.support.annotation.NonNull;
+import android.support.v4.app.JobIntentService;
 import android.text.TextUtils;
 
+import org.mozilla.gecko.JobIdsConstants;
 import org.mozilla.gecko.background.common.log.Logger;
 import org.mozilla.gecko.background.fxa.FxAccountClient20;
 import org.mozilla.gecko.background.fxa.FxAccountClientException;
 import org.mozilla.gecko.background.fxa.oauth.FxAccountAbstractClient;
 import org.mozilla.gecko.background.fxa.oauth.FxAccountAbstractClientException.FxAccountAbstractClientRemoteException;
 import org.mozilla.gecko.background.fxa.oauth.FxAccountOAuthClient10;
 import org.mozilla.gecko.db.BrowserContract;
 import org.mozilla.gecko.fxa.FxAccountConstants;
-import org.mozilla.gecko.fxa.authenticator.AndroidFxAccount;
 import org.mozilla.gecko.fxa.sync.FxAccountNotificationManager;
 import org.mozilla.gecko.fxa.sync.FxAccountSyncAdapter;
 import org.mozilla.gecko.sync.ExtendedJSONObject;
 import org.mozilla.gecko.sync.repositories.android.BrowserContractHelpers;
 import org.mozilla.gecko.sync.repositories.android.ClientsDatabase;
 import org.mozilla.gecko.sync.repositories.android.FennecTabsRepository;
 
 import java.util.concurrent.Executor;
@@ -35,31 +36,25 @@ import java.util.concurrent.Executors;
 /**
  * A background service to clean up after a Firefox Account is deleted.
  * <p>
  * Note that we specifically handle deleting the pickle file using a Service and a
  * BroadcastReceiver, rather than a background thread, to allow channels sharing a Firefox account
  * to delete their respective pickle files (since, if one remains, the account will be restored
  * when that channel is used).
  */
-public class FxAccountDeletedService extends IntentService {
+public class FxAccountDeletedService extends JobIntentService {
   public static final String LOG_TAG = FxAccountDeletedService.class.getSimpleName();
 
-  public FxAccountDeletedService() {
-    super(LOG_TAG);
+  public static void enqueueWork(@NonNull final Context context, @NonNull final Intent workIntent) {
+    enqueueWork(context, FxAccountDeletedService.class, JobIdsConstants.getIdForProfileDeleteJob(), workIntent);
   }
 
   @Override
-  protected void onHandleIntent(final Intent intent) {
-    // Intent can, in theory, be null. Bug 1025937.
-    if (intent == null) {
-      Logger.debug(LOG_TAG, "Short-circuiting on null intent.");
-      return;
-    }
-
+  protected void onHandleWork(@NonNull Intent intent) {
     final Context context = this;
 
     long intentVersion = intent.getLongExtra(
         FxAccountConstants.ACCOUNT_DELETED_INTENT_VERSION_KEY, 0);
     long expectedVersion = FxAccountConstants.ACCOUNT_DELETED_INTENT_VERSION;
     if (intentVersion != expectedVersion) {
       Logger.warn(LOG_TAG, "Intent malformed: version " + intentVersion + " given but " +
           "version " + expectedVersion + "expected. Not cleaning up after deleted Account.");