--- a/mobile/android/base/java/org/mozilla/gecko/BrowserApp.java
+++ b/mobile/android/base/java/org/mozilla/gecko/BrowserApp.java
@@ -7,16 +7,17 @@ package org.mozilla.gecko;
 
 import android.Manifest;
 import android.annotation.TargetApi;
 import android.app.DownloadManager;
 import android.content.ContentProviderClient;
 import android.os.Environment;
 import android.os.Process;
 import android.support.annotation.NonNull;
+import android.support.annotation.Nullable;
 import android.support.annotation.UiThread;
 
 import org.mozilla.gecko.activitystream.ActivityStream;
 import org.mozilla.gecko.adjust.AdjustBrowserAppDelegate;
 import org.mozilla.gecko.annotation.RobocopTarget;
 import org.mozilla.gecko.AppConstants.Versions;
 import org.mozilla.gecko.DynamicToolbar.VisibilityTransition;
 import org.mozilla.gecko.Tabs.TabEvents;
@@ -173,19 +174,21 @@ import org.mozilla.gecko.switchboard.Swi
 import java.io.File;
 import java.io.FileNotFoundException;
 import java.io.IOException;
 import java.lang.reflect.Method;
 import java.net.URLEncoder;
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.EnumSet;
+import java.util.HashMap;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Locale;
+import java.util.Map;
 import java.util.Vector;
 import java.util.regex.Pattern;
 
 public class BrowserApp extends GeckoApp
                         implements TabsPanel.TabsLayoutChangeListener,
                                    PropertyAnimator.PropertyAnimationListener,
                                    View.OnKeyListener,
                                    DynamicToolbarAnimator.MetricsListener,
@@ -248,29 +251,31 @@ 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;
+    // Mirrors toolsMenuID in browser.js menu
+    private static final String GECKO_TOOLS_MENU = "687c5a90-591d-4979-835d-066413a107e2";
     private static final int ADDON_MENU_OFFSET = 1000;
     public static final String TAB_HISTORY_FRAGMENT_TAG = "tabHistoryFragment";
 
     private static class MenuItemInfo {
         public String id;
         public String label;
         public int position;
         public boolean checkable;
         public boolean checked;
         public boolean enabled = true;
         public boolean visible = true;
-        public int parent;
+        // points to id of the parent menu, null if parent should be the main app menu
+        public String parent;
         public boolean added;   // So we can re-add after a locale change.
     }
 
     // The types of guest mode dialogs we show.
     public static enum GuestModeDialog {
         ENTERING,
         LEAVING
     }
@@ -1810,18 +1815,17 @@ public class BrowserApp extends GeckoApp
                     return;
                 }
                 info.id = message.getString("id");
                 info.position = ADDON_MENU_OFFSET + mNextAddonMenuId;
                 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;
+                info.parent = message.getString("parent", null);
                 addAddonMenuItem(info);
                 mNextAddonMenuId++;
                 break;
 
             case "Menu:Remove":
                 removeAddonMenuItem(message.getString("id"));
                 break;
 
@@ -3055,51 +3059,65 @@ public class BrowserApp extends GeckoApp
                     return parent;
                 }
             }
         }
 
         return null;
     }
 
+    private final Map<String, Integer> menuUUIDToIndexMap = new HashMap<>();
+
+    private @Nullable MenuItem findItemWithUUID(final Menu menu, final String uuid) {
+        final Integer index = menuUUIDToIndexMap.get(uuid);
+        if (index != null) {
+            return menu.findItem(index);
+        }
+
+        return null;
+    }
+
     /**
      * Add the provided item to the provided menu, which should be
      * the root (mMenu).
      */
     private void addAddonMenuItemToMenu(final Menu menu, final MenuItemInfo info) {
         info.added = true;
 
         final Menu destination;
-        if (info.parent == 0) {
+        if (info.parent == null) {
             destination = menu;
-        } else if (info.parent == GECKO_TOOLS_MENU) {
+        } else if (GECKO_TOOLS_MENU.equals(info.parent)) {
             // 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);
+            final MenuItem parent = findItemWithUUID(menu, info.parent);
             if (parent == null) {
                 return;
             }
 
             Menu parentMenu = findParentMenu(menu, parent);
 
             if (!parent.hasSubMenu()) {
                 parentMenu.removeItem(parent.getItemId());
                 destination = parentMenu.addSubMenu(Menu.NONE, parent.getItemId(), Menu.NONE, parent.getTitle());
+
                 if (parent.getIcon() != null) {
                     ((SubMenu) destination).getItem().setIcon(parent.getIcon());
                 }
             } else {
                 destination = parent.getSubMenu();
             }
         }
 
         final MenuItem item = destination.add(Menu.NONE, info.position, Menu.NONE, info.label);
 
+        menuUUIDToIndexMap.put(info.id, item.getItemId());
+
         item.setOnMenuItemClickListener(new MenuItem.OnMenuItemClickListener() {
             @Override
             public boolean onMenuItemClick(MenuItem item) {
                 final GeckoBundle data = new GeckoBundle(1);
                 data.putString("item", info.id);
                 EventDispatcher.getInstance().dispatch("Menu:Clicked", data);
                 return true;
             }
@@ -3196,16 +3214,17 @@ public class BrowserApp extends GeckoApp
             HardwareUtils.isTablet()) {
             ((GeckoMenu) menu).setActionItemBarPresenter(mBrowserToolbar);
         }
 
         MenuInflater inflater = getMenuInflater();
         inflater.inflate(R.menu.browser_app_menu, mMenu);
 
         // Add add-on menu items, if any exist.
+        menuUUIDToIndexMap.clear();
         if (mAddonMenuItemsCache != null && !mAddonMenuItemsCache.isEmpty()) {
             for (MenuItemInfo item : mAddonMenuItemsCache) {
                 addAddonMenuItemToMenu(mMenu, item);
             }
         }
 
         // Action providers are available only ICS+.
         GeckoMenuItem share = (GeckoMenuItem) mMenu.findItem(R.id.share);

--- a/mobile/android/chrome/content/browser.js
+++ b/mobile/android/chrome/content/browser.js
@@ -2257,17 +2257,18 @@ var NativeWindow = {
     GlobalEventDispatcher.sendRequest({
       type: "Dex:Unload",
       zipfile: zipFile
     });
   },
 
   menu: {
     _callbacks: [],
-    toolsMenuID: -1,
+    // Mirrors "GECKO_TOOLS_MENU" in BrowserApp.java
+    toolsMenuID: "687c5a90-591d-4979-835d-066413a107e2",
     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],