--- a/browser/components/extensions/.eslintrc
+++ b/browser/components/extensions/.eslintrc
@@ -1,15 +1,16 @@
 {
   "extends": "../../../toolkit/components/extensions/.eslintrc",
 
   "globals": {
     "AllWindowEvents": true,
     "currentWindow": true,
     "EventEmitter": true,
+    "getCookieStoreIdForTab": true,
     "IconDetails": true,
     "makeWidgetId": true,
     "pageActionFor": true,
     "PanelPopup": true,
     "TabContext": true,
     "ViewPopup": true,
     "WindowEventManager": true,
     "WindowListManager": true,

--- a/browser/components/extensions/ext-utils.js
+++ b/browser/components/extensions/ext-utils.js
@@ -701,16 +701,19 @@ ExtensionTabManager.prototype = {
       pinned: tab.pinned,
       status: TabManager.getStatus(tab),
       incognito: PrivateBrowsingUtils.isBrowserPrivate(browser),
       width: browser.frameLoader.lazyWidth || browser.clientWidth,
       height: browser.frameLoader.lazyHeight || browser.clientHeight,
       audible: tab.soundPlaying,
       mutedInfo,
     };
+    if (this.extension.hasPermission("cookies")) {
+      result.cookieStoreId = getCookieStoreIdForTab(result);
+    }
 
     if (this.hasTabPermission(tab)) {
       result.url = browser.currentURI.spec;
       let title = browser.contentTitle || tab.label;
       if (title) {
         result.title = title;
       }
       let icon = window.gBrowser.getIcon(tab);

--- a/toolkit/components/extensions/.eslintrc
+++ b/toolkit/components/extensions/.eslintrc
@@ -18,16 +18,17 @@
     "NetUtil": true,
     "openOptionsPage": true,
     "require": false,
     "runSafe": true,
     "runSafeSync": true,
     "runSafeSyncWithoutClone": true,
     "Services": true,
     "TabManager": true,
+    "WindowListManager": true,
     "XPCOMUtils": true,
   },
 
   "rules": {
     // Rules from the mozilla plugin
     "mozilla/balanced-listeners": 2,
     "mozilla/mark-test-function-used": 1,
     "mozilla/no-aArgs": 1,

--- a/toolkit/components/extensions/ext-cookies.js
+++ b/toolkit/components/extensions/ext-cookies.js
@@ -4,30 +4,34 @@ const {interfaces: Ci, utils: Cu} = Comp
 
 Cu.import("resource://gre/modules/ExtensionUtils.jsm");
 Cu.import("resource://gre/modules/NetUtil.jsm");
 
 var {
   EventManager,
 } = ExtensionUtils;
 
-// Cookies from private tabs currently can't be enumerated.
 var DEFAULT_STORE = "firefox-default";
+var PRIVATE_STORE = "firefox-private";
 
-function convert(cookie) {
+global.getCookieStoreIdForTab = function(tab) {
+  return tab.incognito ? PRIVATE_STORE : DEFAULT_STORE;
+};
+
+function convert({cookie, isPrivate}) {
   let result = {
     name: cookie.name,
     value: cookie.value,
     domain: cookie.host,
     hostOnly: !cookie.isDomain,
     path: cookie.path,
     secure: cookie.isSecure,
     httpOnly: cookie.isHttpOnly,
     session: cookie.isSession,
-    storeId: DEFAULT_STORE,
+    storeId: isPrivate ? PRIVATE_STORE : DEFAULT_STORE,
   };
 
   if (!cookie.isSession) {
     result.expirationDate = cookie.expiry;
   }
 
   return result;
 }
@@ -121,45 +125,60 @@ function checkSetCookiePermissions(exten
 
   // We don't do any significant checking of path permissions. RFC2109
   // suggests we only allow sites to add cookies for sub-paths, similar to
   // same origin policy enforcement, but no-one implements this.
 
   return true;
 }
 
-function* query(detailsIn, props, extension) {
+function* query(detailsIn, props, context) {
   // Different callers want to filter on different properties. |props|
   // tells us which ones they're interested in.
   let details = {};
   props.forEach(property => {
     if (detailsIn[property] !== null) {
       details[property] = detailsIn[property];
     }
   });
 
   if ("domain" in details) {
     details.domain = details.domain.toLowerCase().replace(/^\./, "");
   }
 
+  let isPrivate = context.incognito;
+  if (details.storeId == DEFAULT_STORE) {
+    isPrivate = false;
+  } else if (details.storeId == PRIVATE_STORE) {
+    isPrivate = true;
+  } else if ("storeId" in details) {
+    return;
+  }
+
   // We can use getCookiesFromHost for faster searching.
   let enumerator;
   let uri;
   if ("url" in details) {
     try {
       uri = NetUtil.newURI(details.url).QueryInterface(Ci.nsIURL);
-      enumerator = Services.cookies.getCookiesFromHost(uri.host, {});
+      Services.cookies.usePrivateMode(isPrivate, () => {
+        enumerator = Services.cookies.getCookiesFromHost(uri.host, {});
+      });
     } catch (ex) {
       // This often happens for about: URLs
       return;
     }
   } else if ("domain" in details) {
-    enumerator = Services.cookies.getCookiesFromHost(details.domain, {});
+    Services.cookies.usePrivateMode(isPrivate, () => {
+      enumerator = Services.cookies.getCookiesFromHost(details.domain, {});
+    });
   } else {
-    enumerator = Services.cookies.enumerator;
+    Services.cookies.usePrivateMode(isPrivate, () => {
+      enumerator = Services.cookies.enumerator;
+    });
   }
 
   // Based on nsCookieService::GetCookieStringInternal
   function matches(cookie) {
     function domainMatches(host) {
       return cookie.rawHost == host || (cookie.isDomain && host.endsWith(cookie.host));
     }
 
@@ -213,53 +232,49 @@ function* query(detailsIn, props, extens
     if ("secure" in details && details.secure != cookie.isSecure) {
       return false;
     }
 
     if ("session" in details && details.session != cookie.isSession) {
       return false;
     }
 
-    if ("storeId" in details && details.storeId != DEFAULT_STORE) {
-      return false;
-    }
-
     // Check that the extension has permissions for this host.
-    if (!extension.whiteListedHosts.matchesCookie(cookie)) {
+    if (!context.extension.whiteListedHosts.matchesCookie(cookie)) {
       return false;
     }
 
     return true;
   }
 
   while (enumerator.hasMoreElements()) {
     let cookie = enumerator.getNext().QueryInterface(Ci.nsICookie2);
     if (matches(cookie)) {
-      yield cookie;
+      yield {cookie, isPrivate};
     }
   }
 }
 
 extensions.registerSchemaAPI("cookies", "addon_parent", context => {
   let {extension} = context;
   let self = {
     cookies: {
       get: function(details) {
         // FIXME: We don't sort by length of path and creation time.
-        for (let cookie of query(details, ["url", "name", "storeId"], extension)) {
+        for (let cookie of query(details, ["url", "name", "storeId"], context)) {
           return Promise.resolve(convert(cookie));
         }
 
         // Found no match.
         return Promise.resolve(null);
       },
 
       getAll: function(details) {
         let allowed = ["url", "name", "domain", "path", "secure", "session", "storeId"];
-        let result = Array.from(query(details, allowed, extension), convert);
+        let result = Array.from(query(details, allowed, context), convert);
 
         return Promise.resolve(result);
       },
 
       set: function(details) {
         let uri = NetUtil.newURI(details.url).QueryInterface(Ci.nsIURL);
 
         let path;
@@ -274,57 +289,86 @@ extensions.registerSchemaAPI("cookies", 
         }
 
         let name = details.name !== null ? details.name : "";
         let value = details.value !== null ? details.value : "";
         let secure = details.secure !== null ? details.secure : false;
         let httpOnly = details.httpOnly !== null ? details.httpOnly : false;
         let isSession = details.expirationDate === null;
         let expiry = isSession ? Number.MAX_SAFE_INTEGER : details.expirationDate;
-        // Ignore storeID.
+        let isPrivate = context.incognito;
+        if (details.storeId == DEFAULT_STORE) {
+          isPrivate = false;
+        } else if (details.storeId == PRIVATE_STORE) {
+          isPrivate = true;
+        } else if (details.storeId !== null) {
+          return Promise.reject({message: "Unknown storeId"});
+        }
 
         let cookieAttrs = {host: details.domain, path: path, isSecure: secure};
         if (!checkSetCookiePermissions(extension, uri, cookieAttrs)) {
           return Promise.reject({message: `Permission denied to set cookie ${JSON.stringify(details)}`});
         }
 
         // The permission check may have modified the domain, so use
         // the new value instead.
-        Services.cookies.add(cookieAttrs.host, path, name, value,
-                             secure, httpOnly, isSession, expiry, {});
+        Services.cookies.usePrivateMode(isPrivate, () => {
+          Services.cookies.add(cookieAttrs.host, path, name, value,
+                               secure, httpOnly, isSession, expiry, {});
+        });
 
         return self.cookies.get(details);
       },
 
       remove: function(details) {
-        for (let cookie of query(details, ["url", "name", "storeId"], extension)) {
-          Services.cookies.remove(cookie.host, cookie.name, cookie.path, false, cookie.originAttributes);
+        for (let {cookie, isPrivate} of query(details, ["url", "name", "storeId"], context)) {
+          Services.cookies.usePrivateMode(isPrivate, () => {
+            Services.cookies.remove(cookie.host, cookie.name, cookie.path, false, cookie.originAttributes);
+          });
           // Todo: could there be multiple per subdomain?
           return Promise.resolve({
             url: details.url,
             name: details.name,
-            storeId: DEFAULT_STORE,
+            storeId: isPrivate ? PRIVATE_STORE : DEFAULT_STORE,
           });
         }
 
         return Promise.resolve(null);
       },
 
       getAllCookieStores: function() {
-        // Todo: list all the tabIds for non-private tabs
-        return Promise.resolve([{id: DEFAULT_STORE, tabIds: []}]);
+        let defaultTabs = [];
+        let privateTabs = [];
+        for (let window of WindowListManager.browserWindows()) {
+          let tabs = TabManager.for(extension).getTabs(window);
+          for (let tab of tabs) {
+            if (tab.incognito) {
+              privateTabs.push(tab.id);
+            } else {
+              defaultTabs.push(tab.id);
+            }
+          }
+        }
+        let result = [];
+        if (defaultTabs.length > 0) {
+          result.push({id: DEFAULT_STORE, tabIds: defaultTabs});
+        }
+        if (privateTabs.length > 0) {
+          result.push({id: PRIVATE_STORE, tabIds: privateTabs});
+        }
+        return Promise.resolve(result);
       },
 
       onChanged: new EventManager(context, "cookies.onChanged", fire => {
         let observer = (subject, topic, data) => {
           let notify = (removed, cookie, cause) => {
             cookie.QueryInterface(Ci.nsICookie2);
 
             if (extension.whiteListedHosts.matchesCookie(cookie)) {
-              fire({removed, cookie: convert(cookie), cause});
+              fire({removed, cookie: convert({cookie, isPrivate: topic == "private-cookie-changed"}), cause});
             }
           };
 
           // We do our best effort here to map the incompatible states.
           switch (data) {
             case "deleted":
               notify(true, subject, "explicit");
               break;
@@ -345,15 +389,19 @@ extensions.registerSchemaAPI("cookies", 
                   notify(true, cookie, "evicted");
                 }
               }
               break;
           }
         };
 
         Services.obs.addObserver(observer, "cookie-changed", false);
-        return () => Services.obs.removeObserver(observer, "cookie-changed");
+        Services.obs.addObserver(observer, "private-cookie-changed", false);
+        return () => {
+          Services.obs.removeObserver(observer, "cookie-changed");
+          Services.obs.removeObserver(observer, "private-cookie-changed");
+        };
       }).api(),
     },
   };
 
   return self;
 });

--- a/toolkit/components/extensions/test/mochitest/mochitest.ini
+++ b/toolkit/components/extensions/test/mochitest/mochitest.ini
@@ -75,16 +75,17 @@ skip-if = (os == 'android' || buildapp =
 skip-if = (os == 'android' || buildapp == 'b2g') # sender.tab is undefined on b2g. Bug 1258975 on android.
 [test_ext_sendmessage_doublereply.html]
 skip-if = (os == 'android' || buildapp == 'b2g') # sender.tab is undefined on b2g. Bug 1258975 on android.
 [test_ext_sendmessage_no_receiver.html]
 [test_ext_storage_content.html]
 [test_ext_storage_tab.html]
 skip-if = os == 'android' # Android does not currently support tabs.
 [test_ext_cookies.html]
+skip-if = (os == 'android' || buildapp == 'b2g') # needs TabManager which is not yet implemented. Bug 1258975 on android.
 [test_ext_background_api_injection.html]
 [test_ext_background_generated_url.html]
 [test_ext_background_teardown.html]
 [test_ext_tab_teardown.html]
 skip-if = (os == 'android') # Android does not support tabs API. Bug 1260250
 [test_ext_unload_frame.html]
 [test_ext_i18n.html]
 skip-if = (os == 'android') # Bug 1258975 on android.

--- a/toolkit/components/extensions/test/mochitest/test_ext_cookies.html
+++ b/toolkit/components/extensions/test/mochitest/test_ext_cookies.html
@@ -25,16 +25,17 @@ add_task(function* test_cookies() {
 
     const TEST_URL = "http://example.org/";
     const TEST_SECURE_URL = "https://example.org/";
     const THE_FUTURE = Date.now() + 5 * 60;
     const TEST_PATH = "set_path";
     const TEST_URL_WITH_PATH = TEST_URL + TEST_PATH;
     const TEST_COOKIE_PATH = `/${TEST_PATH}`;
     const STORE_ID = "firefox-default";
+    const PRIVATE_STORE_ID = "firefox-private";
 
     let expected = {
       name: "name1",
       value: "value1",
       domain: "example.org",
       hostOnly: true,
       path: "/",
       secure: false,
@@ -79,17 +80,28 @@ add_task(function* test_cookies() {
       assertExpected({url: TEST_URL, name: "name1", storeId: STORE_ID}, details);
       return browser.cookies.get({url: TEST_URL, name: "name1"});
     }).then(cookie => {
       browser.test.assertEq(null, cookie, "removed cookie not found");
       return browser.cookies.getAllCookieStores();
     }).then(stores => {
       browser.test.assertEq(1, stores.length, "expected number of stores returned");
       browser.test.assertEq(STORE_ID, stores[0].id, "expected store id returned");
-      browser.test.assertEq(0, stores[0].tabIds.length, "no tabs returned for store"); // Todo: Implement this.
+      browser.test.assertEq(1, stores[0].tabIds.length, "one tab returned for store");
+      return browser.windows.create({incognito: true});
+    }).then(privateWindow => {
+      return browser.cookies.getAllCookieStores().then(stores => {
+        browser.test.assertEq(2, stores.length, "expected number of stores returned");
+        browser.test.assertEq(STORE_ID, stores[0].id, "expected store id returned");
+        browser.test.assertEq(1, stores[0].tabIds.length, "one tab returned for store");
+        browser.test.assertEq(PRIVATE_STORE_ID, stores[1].id, "expected private store id returned");
+        browser.test.assertEq(1, stores[0].tabIds.length, "one tab returned for private store");
+        return browser.windows.remove(privateWindow.id);
+      });
+    }).then(() => {
       return browser.cookies.set({url: TEST_URL, name: "name2", domain: ".example.org", expirationDate: THE_FUTURE});
     }).then(cookie => {
       browser.test.assertEq(false, cookie.hostOnly, "cookie is not a hostOnly cookie");
       return browser.cookies.remove({url: TEST_URL, name: "name2"});
     }).then(details => {
       assertExpected({url: TEST_URL, name: "name2", storeId: STORE_ID}, details);
       // Create a session cookie.
       return browser.cookies.set({url: TEST_URL, name: "name1", value: "value1"});
@@ -158,16 +170,44 @@ add_task(function* test_cookies() {
       return browser.cookies.remove({url: TEST_URL, name: "name1"});
     }).then(details => {
       assertExpected({url: TEST_URL, name: "name1", storeId: STORE_ID}, details);
       return browser.cookies.set({url: TEST_URL});
     }).then(cookie => {
       browser.test.assertEq("", cookie.name, "default name set");
       browser.test.assertEq("", cookie.value, "default value set");
       browser.test.assertEq(true, cookie.session, "no expiry date created session cookie");
+      return browser.windows.create({incognito: true});
+    }).then(privateWindow => {
+      return browser.cookies.set({url: TEST_URL, name: "store", value: "private", expirationDate: THE_FUTURE, storeId: PRIVATE_STORE_ID}).then(cookie => {
+        return browser.cookies.set({url: TEST_URL, name: "store", value: "default", expirationDate: THE_FUTURE, storeId: STORE_ID});
+      }).then(cookie => {
+        return browser.cookies.get({url: TEST_URL, name: "store", storeId: PRIVATE_STORE_ID});
+      }).then(cookie => {
+        browser.test.assertEq("private", cookie.value, "get the private cookie");
+        browser.test.assertEq(PRIVATE_STORE_ID, cookie.storeId, "get the private cookie storeId");
+        return browser.cookies.get({url: TEST_URL, name: "store", storeId: STORE_ID});
+      }).then(cookie => {
+        browser.test.assertEq("default", cookie.value, "get the default cookie");
+        browser.test.assertEq(STORE_ID, cookie.storeId, "get the default cookie storeId");
+        return browser.cookies.remove({url: TEST_URL, name: "store", storeId: STORE_ID});
+      }).then(details => {
+        assertExpected({url: TEST_URL, name: "store", storeId: STORE_ID}, details);
+        return browser.cookies.get({url: TEST_URL, name: "store", storeId: STORE_ID});
+      }).then(cookie => {
+        browser.test.assertEq(null, cookie, "deleted the default cookie");
+        return browser.cookies.remove({url: TEST_URL, name: "store", storeId: PRIVATE_STORE_ID});
+      }).then(details => {
+        assertExpected({url: TEST_URL, name: "store", storeId: PRIVATE_STORE_ID}, details);
+        return browser.cookies.get({url: TEST_URL, name: "store", storeId: PRIVATE_STORE_ID});
+      }).then(cookie => {
+        browser.test.assertEq(null, cookie, "deleted the private cookie");
+        return browser.windows.remove(privateWindow.id);
+      });
+    }).then(() => {
       browser.test.notifyPass("cookies");
     });
   }
 
   let extension = ExtensionTestUtils.loadExtension({
     background,
     manifest: {
       permissions: ["cookies", "*://example.org/"],