--- a/mobile/android/base/java/org/mozilla/gecko/BrowserApp.java
+++ b/mobile/android/base/java/org/mozilla/gecko/BrowserApp.java
@@ -212,16 +212,17 @@ public class BrowserApp extends GeckoApp
     private static final String INTENT_KEY_SWITCHBOARD_SERVER = "switchboard-server";
 
     // TODO: Replace with kinto endpoint.
     private static final String SWITCHBOARD_SERVER = "https://firefox.settings.services.mozilla.com/v1/buckets/fennec/collections/experiments/records";
 
     private static final String STATE_ABOUT_HOME_TOP_PADDING = "abouthome_top_padding";
     private static final String STATE_ADDON_MENU_ITEM_CACHE = "menuitems_cache";
     private static final String STATE_BROWSER_ACTION_ITEM_CACHE = "browseractions_cache";
+    private static final String STATE_ADDON_MENU_NEXT_ID = "menuitems_nextId";
 
     private static final String BROWSER_SEARCH_TAG = "browser_search";
 
     // Request ID for startActivityForResult.
     public static final int ACTIVITY_REQUEST_PREFERENCES = 1001;
     private static final int ACTIVITY_REQUEST_TAB_QUEUE = 2001;
     public static final int ACTIVITY_REQUEST_FIRST_READERVIEW_BOOKMARK = 3001;
     public static final int ACTIVITY_RESULT_FIRST_READERVIEW_BOOKMARKS_GOTO_BOOKMARKS = 3002;
@@ -259,17 +260,16 @@ public class BrowserApp extends GeckoApp
     private int mCachedRecentTabsCount;
     private ActionModeCompat mActionMode;
     private TabHistoryController tabHistoryController;
 
     private static final int GECKO_TOOLS_MENU_ID = -1;
     // When changing this, make sure to adjust NativeWindow.toolsMenuID in browser.js, too.
     private static final String GECKO_TOOLS_MENU_UUID = "{115b9308-2023-44f1-a4e9-3e2197669f07}";
     private static final int ADDON_MENU_OFFSET = 1000;
-    private static final int BROWSER_ACTION_MENU_OFFSET = 10000;
     public static final String TAB_HISTORY_FRAGMENT_TAG = "tabHistoryFragment";
 
     // When the static action bar is shown, only the real toolbar chrome should be
     // shown when the toolbar is visible. Causing the toolbar animator to also
     // show the snapshot causes the content to shift under the users finger.
     // See: Bug 1358554
     private boolean mShowingToolbarChromeForActionBar;
 
@@ -334,16 +334,17 @@ public class BrowserApp extends GeckoApp
     // The types of guest mode dialogs we show.
     public static enum GuestModeDialog {
         ENTERING,
         LEAVING
     }
 
     private ArrayList<MenuItemInfo> mAddonMenuItemsCache;
     private ArrayList<MenuItemInfo> mBrowserActionItemsCache;
+    private int mAddonMenuNextID = ADDON_MENU_OFFSET;
     private PropertyAnimator mMainLayoutAnimator;
 
     private static final Interpolator sTabsInterpolator = new Interpolator() {
         @Override
         public float getInterpolation(float t) {
             t -= 1.0f;
             return t * t * t * t * t + 1.0f;
         }
@@ -746,16 +747,17 @@ public class BrowserApp extends GeckoApp
         });
 
         // If the activity is being restored, the add-ons menu item cache only needs restoring if
         // Gecko is already running. Otherwise, we'll simply catch the corresponding events when
         // Gecko and the add-ons are starting up.
         if (savedInstanceState != null && mIsRestoringActivity) {
             mAddonMenuItemsCache = savedInstanceState.getParcelableArrayList(STATE_ADDON_MENU_ITEM_CACHE);
             mBrowserActionItemsCache = savedInstanceState.getParcelableArrayList(STATE_BROWSER_ACTION_ITEM_CACHE);
+            mAddonMenuNextID = savedInstanceState.getInt(STATE_ADDON_MENU_NEXT_ID);
         }
 
         app.getLightweightTheme().addListener(this);
 
         mProgressView = (AnimatedProgressBar) findViewById(R.id.page_progress);
         mDynamicToolbar.setLayerView(mLayerView);
         mProgressView.setDynamicToolbar(mDynamicToolbar);
         mBrowserToolbar.setProgressBar(mProgressView);
@@ -1864,17 +1866,17 @@ public class BrowserApp extends GeckoApp
 
             case "Menu:Add":
                 final MenuItemInfo info = new MenuItemInfo();
                 info.label = message.getString("name");
                 if (info.label == null) {
                     Log.e(LOGTAG, "Invalid menu item name");
                     return;
                 }
-                info.id = message.getInt("id") + ADDON_MENU_OFFSET;
+                info.id = mAddonMenuNextID++;
                 info.uuid = message.getString("uuid");
                 info.checked = message.getBoolean("checked", false);
                 info.enabled = message.getBoolean("enabled", true);
                 info.visible = message.getBoolean("visible", true);
                 info.checkable = message.getBoolean("checkable", false);
                 final String parentUUID = message.getString("parent");
                 if (GECKO_TOOLS_MENU_UUID.equals(parentUUID)) {
                     info.parent = GECKO_TOOLS_MENU_ID;
@@ -1895,17 +1897,17 @@ public class BrowserApp extends GeckoApp
 
             case "Menu:AddBrowserAction":
                 final MenuItemInfo browserAction = new MenuItemInfo();
                 browserAction.label = message.getString("name");
                 if (TextUtils.isEmpty(browserAction.label)) {
                     Log.e(LOGTAG, "Invalid browser action name");
                     return;
                 }
-                browserAction.id = message.getInt("id") + BROWSER_ACTION_MENU_OFFSET;
+                browserAction.id = mAddonMenuNextID++;
                 browserAction.uuid = message.getString("uuid");
                 addBrowserActionMenuItem(browserAction);
                 break;
 
             case "Menu:RemoveBrowserAction":
                 removeBrowserActionMenuItem(message.getString("uuid"));
                 break;
 
@@ -2439,16 +2441,17 @@ public class BrowserApp extends GeckoApp
         // The various add-on UI item caches and event listeners should really live somewhere based
         // on the Application, so that their lifetime more closely matches that of Gecko itself, as
         // GeckoView-based activities can start Gecko (and therefore add-ons) while BrowserApp isn't
         // even running.
         // For now we'll only guard against the case where BrowserApp is destroyed and later re-
         // created while Gecko keeps running throughout, and leave the full solution to bug 1414084.
         outState.putParcelableArrayList(STATE_ADDON_MENU_ITEM_CACHE, mAddonMenuItemsCache);
         outState.putParcelableArrayList(STATE_BROWSER_ACTION_ITEM_CACHE, mBrowserActionItemsCache);
+        outState.putInt(STATE_ADDON_MENU_NEXT_ID, mAddonMenuNextID);
     }
 
     /**
      * Attempts to switch to an open tab with the given URL.
      * <p>
      * If the tab exists, this method cancels any in-progress editing as well as
      * calling {@link Tabs#selectTab(int)}.
      *

--- a/mobile/android/chrome/content/browser.js
+++ b/mobile/android/chrome/content/browser.js
@@ -2320,17 +2320,16 @@ var NativeWindow = {
       "Doorhanger:Reply",
       "Menu:Clicked",
     ]);
     this.contextmenus.init();
   },
 
   menu: {
     _callbacks: [],
-    _menuId: 1,
     // This value must be kept in sync with GECKO_TOOLS_MENU_UUID in BrowserApp.java.
     toolsMenuID: "{115b9308-2023-44f1-a4e9-3e2197669f07}",
     add: function() {
       let options;
       if (arguments.length == 1) {
         options = arguments[0];
       } else if (arguments.length == 3) {
           Log.w("Browser", "This menu addon API has been deprecated. Instead, use the options object API.");
@@ -2338,22 +2337,20 @@ var NativeWindow = {
             name: arguments[0],
             callback: arguments[2]
           };
       } else {
          throw "Incorrect number of parameters";
       }
 
       options.type = "Menu:Add";
-      options.id = this._menuId;
       options.uuid = uuidgen.generateUUID().toString();
 
       GlobalEventDispatcher.sendRequest(options);
       this._callbacks[options.uuid] = options.callback;
-      this._menuId++;
       return options.uuid;
     },
 
     remove: function(aUuid) {
       GlobalEventDispatcher.sendRequest({ type: "Menu:Remove", uuid: aUuid });
     },
 
     update: function(aUuid, aOptions) {

--- a/mobile/android/modules/BrowserActions.jsm
+++ b/mobile/android/modules/BrowserActions.jsm
@@ -11,18 +11,16 @@ ChromeUtils.import("resource://gre/modul
 var EXPORTED_SYMBOLS = ["BrowserActions"];
 
 var BrowserActions = {
   _browserActions: {},
   _browserActionTitles: {},
 
   _initialized: false,
 
-  _nextMenuId: 0,
-
   /**
    * Registers the listeners only if they have not been initialized
    * already and there is at least one browser action.
    */
   _maybeRegisterListeners() {
     if (!this._initialized && Object.keys(this._browserActions).length) {
       this._initialized = true;
       EventDispatcher.instance.registerListener(this, "Menu:BrowserActionClicked");
@@ -41,38 +39,37 @@ var BrowserActions = {
   },
 
   /**
    * Called when a browser action is clicked on.
    * @param {string} event The name of the event, which should always
    *    be "Menu:BrowserActionClicked".
    * @param {Object} data An object containing information about the
    *    browser action, which in this case should contain an `item`
-   *    property which is browser action's ID.
+   *    property which is browser action's UUID.
    */
   onEvent(event, data) {
     if (event !== "Menu:BrowserActionClicked") {
       throw new Error(`Expected "Menu:BrowserActionClicked" event - received "${event}" instead`);
     }
 
     let browserAction = this._browserActions[data.item];
     if (!browserAction) {
-      throw new Error(`No browser action found with id ${data.item}`);
+      throw new Error(`No browser action found with UUID ${data.item}`);
     }
     browserAction.onClicked();
   },
 
   /**
    * Registers a new browser action.
    * @param {Object} browserAction The browser action to add.
    */
   register(browserAction) {
     EventDispatcher.instance.sendRequest({
       type: "Menu:AddBrowserAction",
-      id: this._nextMenuId++,
       uuid: browserAction.uuid,
       name: browserAction.defaults.name,
     });
 
     this._browserActions[browserAction.uuid] = browserAction;
     this._browserActionTitles[browserAction.uuid] = browserAction.defaults.name;
 
     this._maybeRegisterListeners();
@@ -122,17 +119,17 @@ var BrowserActions = {
     let browserAction = this._browserActions[uuid];
     if (!browserAction) {
       throw new Error(`No BrowserAction with UUID ${uuid} was found`);
     }
     browserAction.onClicked();
   },
 
   /**
-   * Unregisters the browser action with the specified ID.
+   * Unregisters the browser action with the specified UUID.
    * @param {string} uuid The UUID of the browser action.
    */
   unregister(uuid) {
     let browserAction = this._browserActions[uuid];
     if (!browserAction) {
       throw new Error(`No BrowserAction with UUID ${uuid} was found`);
     }
     EventDispatcher.instance.sendRequest({