new file mode 100644
--- /dev/null
+++ b/mobile/android/app/src/test/java/org/mozilla/gecko/TestAddonUICache.java
@@ -0,0 +1,122 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+package org.mozilla.gecko;
+
+import android.view.Menu;
+import android.view.MenuItem;
+
+import org.junit.After;
+import org.junit.Assert;
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.mockito.ArgumentCaptor;
+import org.mockito.Mock;
+import org.mockito.MockitoAnnotations;
+import org.mozilla.gecko.util.GeckoBundle;
+import org.robolectric.RobolectricTestRunner;
+
+import java.util.ArrayList;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.UUID;
+
+import static org.mockito.Matchers.anyInt;
+import static org.mockito.Matchers.anyString;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.never;
+import static org.mockito.Mockito.times;
+import static org.mockito.Mockito.verify;
+import static org.mockito.Mockito.when;
+
+@RunWith(RobolectricTestRunner.class)
+public class TestAddonUICache {
+    private AddonUICache mAddonUICache;
+    private @Mock Menu mMockMenu;
+    private static final MessageGenerator addonMessage = new AddonMenuMessageGenerator();
+
+    @Before
+    public void setUp() {
+        MockitoAnnotations.initMocks(this);
+        when(mMockMenu.add(anyInt(), anyInt(), anyInt(), anyString())).thenReturn(mock(MenuItem.class));
+
+        mAddonUICache = AddonUICache.getInstance();
+        mAddonUICache.init();
+    }
+
+    @After
+    public void tearDown() {
+        mAddonUICache.reset();
+    }
+
+    @Test
+    public void testMenuMessageDirectForward() {
+        mAddonUICache.onCreateOptionsMenu(mMockMenu);
+        verify(mMockMenu, never()).add(anyInt(), anyInt(), anyInt(), anyString());
+
+        Map<String, GeckoBundle> sentMessages = sendAddonMessages("Menu:Add",
+                addonMessage);
+
+        ArgumentCaptor<String> menuLabel = ArgumentCaptor.forClass(String.class);
+        verify(mMockMenu, times(4)).add(anyInt(), anyInt(), anyInt(), menuLabel.capture());
+
+        List<String> expectedLabels = new ArrayList<>(sentMessages.keySet());
+        Assert.assertEquals(expectedLabels, menuLabel.getAllValues());
+    }
+
+    @Test
+    public void testMenuMessageStoreForward() {
+        Map<String, GeckoBundle> sentMessages = sendAddonMessages("Menu:Add",
+                addonMessage);
+
+        mAddonUICache.onCreateOptionsMenu(mMockMenu);
+        ArgumentCaptor<String> menuLabel = ArgumentCaptor.forClass(String.class);
+        verify(mMockMenu, times(4)).add(anyInt(), anyInt(), anyInt(), menuLabel.capture());
+
+        List<String> expectedLabels = new ArrayList<>(sentMessages.keySet());
+        Assert.assertEquals(expectedLabels, menuLabel.getAllValues());
+    }
+
+    @Test
+    public void testMenuMessageStoreRemoveForward() {
+        Map<String, GeckoBundle> sentMessages = sendAddonMessages("Menu:Add",
+                addonMessage);
+        sendAddonMessages("Menu:Remove", new ArrayList<>(sentMessages.values()));
+
+        mAddonUICache.onCreateOptionsMenu(mMockMenu);
+        verify(mMockMenu, never()).add(anyInt(), anyInt(), anyInt(), anyString());
+    }
+
+    private Map<String, GeckoBundle> sendAddonMessages(String event, MessageGenerator generator) {
+        Map<String, GeckoBundle> sentMessages = new LinkedHashMap<>();
+        for (int i = 0; i < 4; i++) {
+            String label = "Menu " + i;
+            GeckoBundle message = generator.getMessage(label);
+            mAddonUICache.handleMessage(event, message, null);
+            sentMessages.put(label, message);
+        }
+        return sentMessages;
+    }
+
+    private void sendAddonMessages(String event, List<GeckoBundle> messages) {
+        for (GeckoBundle message : messages) {
+            mAddonUICache.handleMessage(event, message, null);
+        }
+    }
+
+    private interface MessageGenerator {
+        GeckoBundle getMessage(String label);
+    }
+
+    private static class AddonMenuMessageGenerator implements MessageGenerator {
+        @Override
+        public GeckoBundle getMessage(String label) {
+            GeckoBundle message = new GeckoBundle(2);
+            message.putString("name", label);
+            message.putString("uuid", "{" + UUID.randomUUID().toString() + "}");
+            return message;
+        }
+    }
+}

--- a/mobile/android/base/java/org/mozilla/gecko/AddonUICache.java
+++ b/mobile/android/base/java/org/mozilla/gecko/AddonUICache.java
@@ -1,16 +1,17 @@
 /* -*- Mode: Java; c-basic-offset: 4; tab-width: 20; indent-tabs-mode: nil; -*-
  * vim: ts=4 sw=4 expandtab:
  * 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;
 
+import android.support.annotation.VisibleForTesting;
 import android.text.TextUtils;
 import android.util.Log;
 import android.view.Menu;
 import android.view.MenuItem;
 import android.view.SubMenu;
 
 import org.mozilla.gecko.util.BundleEventListener;
 import org.mozilla.gecko.util.EventCallback;
@@ -76,16 +77,23 @@ public class AddonUICache implements Bun
             "Menu:Add",
             "Menu:Update",
             "Menu:Remove",
             null);
 
         mInitialized = true;
     }
 
+    @VisibleForTesting
+    /* package, intended private */ void reset() {
+        mAddonMenuItemsCache.clear();
+        mAddonMenuNextID = ADDON_MENU_OFFSET;
+        mMenu = null;
+    }
+
     @Override
     public void handleMessage(String event, GeckoBundle message, EventCallback callback) {
         switch (event) {
             case "Menu:Add":
                 final MenuItemInfo info = new MenuItemInfo();
                 info.label = message.getString("name");
                 if (TextUtils.isEmpty(info.label)) {
                     Log.e(LOGTAG, "Invalid menu item name");