--- 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/background/JobIdsConstants.java
+++ b/mobile/android/services/src/main/java/org/mozilla/gecko/background/JobIdsConstants.java
@@ -12,9 +12,10 @@ public class JobIdsConstants {
     public static final int JOB_ID_DLC_STUDY = -1;
     public static final int JOB_ID_DLC_DOWNLOAD = -2;
     public static final int JOB_ID_DLC_SYNCHRONIZE = -3;
     public static final int JOB_ID_DLC_CLEANUP = -4;
 
     public static final int JOB_ID_TAB_RECEIVED = -5;
 
     public static final int JOB_ID_PROFILE_FETCH = -6;
+    public static final int JOB_ID_PROFILE_DELETE = -7;
 }

--- 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.background.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,25 +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.JOB_ID_PROFILE_DELETE, workIntent);
   }
 
   @Override
-  protected void onHandleIntent(final Intent intent) {
+  protected void onHandleWork(Intent intent) {
     // Intent can, in theory, be null. Bug 1025937.
     if (intent == null) {
       Logger.debug(LOG_TAG, "Short-circuiting on null intent.");
       return;
     }
 
     final Context context = this;