--- a/mobile/android/base/java/org/mozilla/gecko/BrowserApp.java
+++ b/mobile/android/base/java/org/mozilla/gecko/BrowserApp.java
@@ -255,48 +255,52 @@ public class BrowserApp extends GeckoApp
      * home screen implementation (currently that is just the HomePager, but that will be extended
      * to permit further experimental replacement panels such as the activity-stream panel).
      */
     private ViewGroup mHomeScreenContainer;
     private int mCachedRecentTabsCount;
     private ActionModeCompat mActionMode;
     private TabHistoryController tabHistoryController;
 
-    private static final int GECKO_TOOLS_MENU = -1;
+    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;
 
     private SafeIntent safeStartingIntent;
     private Intent startingIntentAfterPip;
     private boolean isInAutomation;
 
     private static class MenuItemInfo implements Parcelable {
         public int id;
+        public String uuid;
         public String label;
         public boolean checkable;
         public boolean checked;
         public boolean enabled = true;
         public boolean visible = true;
         public int parent;
 
         @Override
         public int describeContents() {
             return 0;
         }
 
         @Override
         public void writeToParcel(Parcel dest, int flags) {
             dest.writeInt(id);
+            dest.writeString(uuid);
             dest.writeString(label);
             dest.writeInt(checkable ? 1 : 0);
             dest.writeInt(checked ? 1 : 0);
             dest.writeInt(enabled ? 1 : 0);
             dest.writeInt(visible ? 1 : 0);
             dest.writeInt(parent);
         }
 
@@ -310,65 +314,36 @@ public class BrowserApp extends GeckoApp
             @Override
             public MenuItemInfo[] newArray(int size) {
                 return new MenuItemInfo[size];
             }
         };
 
         private MenuItemInfo(Parcel source) {
             id = source.readInt();
+            uuid = source.readString();
             label = source.readString();
             checkable = source.readInt() != 0;
             checked = source.readInt() != 0;
             enabled = source.readInt() != 0;
             visible = source.readInt() != 0;
             parent = source.readInt();
         }
 
         public MenuItemInfo() { }
     }
 
-    private static class BrowserActionItemInfo extends MenuItemInfo {
-        public String uuid;
-
-        @Override
-        public void writeToParcel(Parcel dest, int flags) {
-            super.writeToParcel(dest, flags);
-            dest.writeString(uuid);
-        }
-
-        public static final Parcelable.Creator<BrowserActionItemInfo> CREATOR
-                = new Parcelable.Creator<BrowserActionItemInfo>() {
-            @Override
-            public BrowserActionItemInfo createFromParcel(Parcel source) {
-                return new BrowserActionItemInfo(source);
-            }
-
-            @Override
-            public BrowserActionItemInfo[] newArray(int size) {
-                return new BrowserActionItemInfo[size];
-            }
-        };
-
-        private BrowserActionItemInfo(Parcel source) {
-            super(source);
-            uuid = source.readString();
-        }
-
-        public BrowserActionItemInfo() { }
-    }
-
     // The types of guest mode dialogs we show.
     public static enum GuestModeDialog {
         ENTERING,
         LEAVING
     }
 
     private ArrayList<MenuItemInfo> mAddonMenuItemsCache;
-    private ArrayList<BrowserActionItemInfo> mBrowserActionItemsCache;
+    private ArrayList<MenuItemInfo> mBrowserActionItemsCache;
     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;
         }
@@ -1878,43 +1853,53 @@ public class BrowserApp extends GeckoApp
             case "Menu:Open":
                 if (mBrowserToolbar.isEditing()) {
                     mBrowserToolbar.cancelEdit();
                 }
                 openOptionsMenu();
                 break;
 
             case "Menu:Update":
-                updateAddonMenuItem(message.getInt("id") + ADDON_MENU_OFFSET,
+                updateAddonMenuItem(message.getString("uuid"),
                                     message.getBundle("options"));
                 break;
 
             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.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 int parent = message.getInt("parent", 0);
-                info.parent = parent <= 0 ? parent : parent + ADDON_MENU_OFFSET;
+                final String parentUUID = message.getString("parent");
+                if (GECKO_TOOLS_MENU_UUID.equals(parentUUID)) {
+                    info.parent = GECKO_TOOLS_MENU_ID;
+                } else if (!TextUtils.isEmpty(parentUUID)) {
+                    for (MenuItemInfo item : mAddonMenuItemsCache) {
+                        if (item.uuid.equals(parentUUID)) {
+                            info.parent = item.id;
+                            break;
+                        }
+                    }
+                }
                 addAddonMenuItem(info);
                 break;
 
             case "Menu:Remove":
-                removeAddonMenuItem(message.getInt("id") + ADDON_MENU_OFFSET);
+                removeAddonMenuItem(message.getString("uuid"));
                 break;
 
             case "Menu:AddBrowserAction":
-                final BrowserActionItemInfo browserAction = new BrowserActionItemInfo();
+                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.uuid = message.getString("uuid");
                 addBrowserActionMenuItem(browserAction);
@@ -3232,17 +3217,17 @@ public class BrowserApp extends GeckoApp
     /**
      * Add the provided item to the provided menu, which should be
      * the root (mMenu).
      */
     private void addAddonMenuItemToMenu(final Menu menu, final MenuItemInfo info) {
         final Menu destination;
         if (info.parent == 0) {
             destination = menu;
-        } else if (info.parent == GECKO_TOOLS_MENU) {
+        } else if (info.parent == GECKO_TOOLS_MENU_ID) {
             // The tools menu only exists in our -v11 resources.
             final MenuItem tools = menu.findItem(R.id.tools);
             destination = tools != null ? tools.getSubMenu() : menu;
         } else {
             final MenuItem parent = menu.findItem(info.parent);
             if (parent == null) {
                 return;
             }
@@ -3288,53 +3273,59 @@ public class BrowserApp extends GeckoApp
 
         if (mMenu == null) {
             return;
         }
 
         addAddonMenuItemToMenu(mMenu, info);
     }
 
-    private void removeAddonMenuItem(int id) {
+    private void removeAddonMenuItem(String uuid) {
+        int id = -1;
+
         // Remove add-on menu item from cache, if available.
         if (mAddonMenuItemsCache != null && !mAddonMenuItemsCache.isEmpty()) {
             for (MenuItemInfo item : mAddonMenuItemsCache) {
-                if (item.id == id) {
+                if (item.uuid.equals(uuid)) {
+                    id = item.id;
                     mAddonMenuItemsCache.remove(item);
                     break;
                 }
             }
         }
 
-        if (mMenu == null) {
+        if (mMenu == null || id == -1) {
             return;
         }
 
         final MenuItem menuItem = mMenu.findItem(id);
         if (menuItem != null) {
             mMenu.removeItem(id);
         }
     }
 
-    private void updateAddonMenuItem(int id, final GeckoBundle options) {
+    private void updateAddonMenuItem(String uuid, final GeckoBundle options) {
+        int id = -1;
+
         // Set attribute for the menu item in cache, if available
         if (mAddonMenuItemsCache != null && !mAddonMenuItemsCache.isEmpty()) {
             for (MenuItemInfo item : mAddonMenuItemsCache) {
-                if (item.id == id) {
+                if (item.uuid.equals(uuid)) {
+                    id = item.id;
                     item.label = options.getString("name", item.label);
                     item.checkable = options.getBoolean("checkable", item.checkable);
                     item.checked = options.getBoolean("checked", item.checked);
                     item.enabled = options.getBoolean("enabled", item.enabled);
                     item.visible = options.getBoolean("visible", item.visible);
                     break;
                 }
             }
         }
 
-        if (mMenu == null) {
+        if (mMenu == null || id == -1) {
             return;
         }
 
         final MenuItem menuItem = mMenu.findItem(id);
         if (menuItem != null) {
             menuItem.setTitle(options.getString("name", menuItem.getTitle().toString()));
             menuItem.setCheckable(options.getBoolean("checkable", menuItem.isCheckable()));
             menuItem.setChecked(options.getBoolean("checked", menuItem.isChecked()));
@@ -3342,17 +3333,17 @@ public class BrowserApp extends GeckoApp
             menuItem.setVisible(options.getBoolean("visible", menuItem.isVisible()));
         }
     }
 
     /**
      * Add the provided item to the provided menu, which should be
      * the root (mMenu).
      */
-    private void addBrowserActionMenuItemToMenu(final Menu menu, final BrowserActionItemInfo info) {
+    private void addBrowserActionMenuItemToMenu(final Menu menu, final MenuItemInfo info) {
         final MenuItem item = menu.add(Menu.NONE, info.id, Menu.NONE, info.label);
 
         item.setOnMenuItemClickListener(new MenuItem.OnMenuItemClickListener() {
             @Override
             public boolean onMenuItemClick(MenuItem item) {
                 final GeckoBundle data = new GeckoBundle(1);
                 data.putString("item", info.uuid);
                 EventDispatcher.getInstance().dispatch("Menu:BrowserActionClicked", data);
@@ -3364,19 +3355,19 @@ public class BrowserApp extends GeckoApp
         item.setChecked(info.checked);
         item.setEnabled(info.enabled);
         item.setVisible(info.visible);
     }
 
     /**
      * Adds a WebExtension browser action to the menu.
      */
-    private void addBrowserActionMenuItem(final BrowserActionItemInfo info) {
+    private void addBrowserActionMenuItem(final MenuItemInfo info) {
         if (mBrowserActionItemsCache == null) {
-            mBrowserActionItemsCache = new ArrayList<BrowserActionItemInfo>();
+            mBrowserActionItemsCache = new ArrayList<>();
         }
 
         // Always cache so we can rebuild after a locale switch.
         mBrowserActionItemsCache.add(info);
 
         if (mMenu == null) {
             return;
         }
@@ -3387,17 +3378,17 @@ public class BrowserApp extends GeckoApp
     /**
      * Removes a WebExtension browser action from the menu by its UUID.
      */
     private void removeBrowserActionMenuItem(String uuid) {
         int id = -1;
 
         // Remove browser action menu item from cache, if available.
         if (mBrowserActionItemsCache != null && !mBrowserActionItemsCache.isEmpty()) {
-            for (BrowserActionItemInfo item : mBrowserActionItemsCache) {
+            for (MenuItemInfo item : mBrowserActionItemsCache) {
                 if (item.uuid.equals(uuid)) {
                     id = item.id;
                     mBrowserActionItemsCache.remove(item);
                     break;
                 }
             }
         }
 
@@ -3414,17 +3405,17 @@ public class BrowserApp extends GeckoApp
     /**
      * Updates the WebExtension browser action with the specified UUID.
      */
     private void updateBrowserActionMenuItem(String uuid, final GeckoBundle options) {
         int id = -1;
 
         // Set attribute for the menu item in cache, if available
         if (mBrowserActionItemsCache != null && !mBrowserActionItemsCache.isEmpty()) {
-            for (BrowserActionItemInfo item : mBrowserActionItemsCache) {
+            for (MenuItemInfo item : mBrowserActionItemsCache) {
                 if (item.uuid.equals(uuid)) {
                     id = item.id;
                     item.label = options.getString("name", item.label);
                     break;
                 }
             }
         }
 
@@ -3449,17 +3440,17 @@ public class BrowserApp extends GeckoApp
             ((GeckoMenu) menu).setActionItemBarPresenter(mBrowserToolbar);
         }
 
         MenuInflater inflater = getMenuInflater();
         inflater.inflate(R.menu.browser_app_menu, mMenu);
 
         // Add browser action menu items, if any exist.
         if (mBrowserActionItemsCache != null && !mBrowserActionItemsCache.isEmpty()) {
-            for (BrowserActionItemInfo item : mBrowserActionItemsCache) {
+            for (MenuItemInfo item : mBrowserActionItemsCache) {
                 addBrowserActionMenuItemToMenu(mMenu, item);
             }
         }
 
         // Add add-on menu items, if any exist.
         if (mAddonMenuItemsCache != null && !mAddonMenuItemsCache.isEmpty()) {
             for (MenuItemInfo item : mAddonMenuItemsCache) {
                 addAddonMenuItemToMenu(mMenu, item);

--- a/mobile/android/chrome/content/browser.js
+++ b/mobile/android/chrome/content/browser.js
@@ -2321,51 +2321,53 @@ var NativeWindow = {
       "Menu:Clicked",
     ]);
     this.contextmenus.init();
   },
 
   menu: {
     _callbacks: [],
     _menuId: 1,
-    toolsMenuID: -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.");
           options = {
             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[this._menuId] = options.callback;
       this._menuId++;
-      return this._menuId - 1;
+      return options.uuid;
     },
 
-    remove: function(aId) {
-      GlobalEventDispatcher.sendRequest({ type: "Menu:Remove", id: aId });
+    remove: function(aUuid) {
+      GlobalEventDispatcher.sendRequest({ type: "Menu:Remove", uuid: aUuid });
     },
 
-    update: function(aId, aOptions) {
+    update: function(aUuid, aOptions) {
       if (!aOptions)
         return;
 
       GlobalEventDispatcher.sendRequest({
         type: "Menu:Update",
-        id: aId,
+        uuid: aUuid,
         options: aOptions
       });
     }
   },
 
   doorhanger: {
     _callbacks: {},
     _callbacksId: 0,