--- a/toolkit/components/url-classifier/SafeBrowsing.jsm
+++ b/toolkit/components/url-classifier/SafeBrowsing.jsm
@@ -125,16 +125,27 @@ this.SafeBrowsing = {
     for (let i = 0; i < this.flashLists.length; ++i) {
       this.registerTableWithURLs(this.flashLists[i]);
     }
     for (let i = 0; i < this.flashInfobarLists.length; ++i) {
       this.registerTableWithURLs(this.flashInfobarLists[i]);
     }
   },
 
+  unregisterTables(obsoleteLists) {
+    let listManager = Cc["@mozilla.org/url-classifier/listmanager;1"].
+      getService(Ci.nsIUrlListManager);
+
+    for (let i = 0; i < obsoleteLists.length; ++i) {
+      for (let j = 0; j < obsoleteLists[i].length; ++j) {
+        listManager.unregisterTable(obsoleteLists[i][j]);
+      }
+    }
+  },
+
 
   initialized:          false,
   phishingEnabled:      false,
   malwareEnabled:       false,
   downloadsEnabled:     false,
   passwordsEnabled:     false,
   trackingEnabled:      false,
   blockedEnabled:       false,
@@ -220,16 +231,31 @@ this.SafeBrowsing = {
     this.blockedEnabled = Services.prefs.getBoolPref("browser.safebrowsing.blockedURIs.enabled");
     this.trackingAnnotations = Services.prefs.getBoolPref("privacy.trackingprotection.annotate_channels");
     this.flashBlockEnabled = Services.prefs.getBoolPref("plugins.flashBlock.enabled");
 
     let flashAllowTable, flashAllowExceptTable, flashTable,
         flashExceptTable, flashSubDocTable,
         flashSubDocExceptTable;
 
+    let obsoleteLists;
+    // Make a copy of the original lists before we re-read the prefs.
+    if (this.initialized) {
+      obsoleteLists = [this.phishingLists,
+                       this.malwareLists,
+                       this.downloadBlockLists,
+                       this.downloadAllowLists,
+                       this.passwordAllowLists,
+                       this.trackingProtectionLists,
+                       this.trackingProtectionWhitelists,
+                       this.blockedLists,
+                       this.flashLists,
+                       this.flashInfobarLists];
+    }
+
     [this.phishingLists,
      this.malwareLists,
      this.downloadBlockLists,
      this.downloadAllowLists,
      this.passwordAllowLists,
      this.trackingProtectionLists,
      this.trackingProtectionWhitelists,
      this.blockedLists,
@@ -242,18 +268,39 @@ this.SafeBrowsing = {
      this.flashInfobarLists] = tablePreferences.map(getLists);
 
     this.flashLists = flashAllowTable.concat(flashAllowExceptTable,
                                              flashTable,
                                              flashExceptTable,
                                              flashSubDocTable,
                                              flashSubDocExceptTable)
 
+    if (obsoleteLists) {
+      let newLists = [this.phishingLists,
+                      this.malwareLists,
+                      this.downloadBlockLists,
+                      this.downloadAllowLists,
+                      this.passwordAllowLists,
+                      this.trackingProtectionLists,
+                      this.trackingProtectionWhitelists,
+                      this.blockedLists,
+                      this.flashLists,
+                      this.flashInfobarLists];
+
+      for (let i = 0; i < obsoleteLists.length; ++i) {
+        obsoleteLists[i] = obsoleteLists[i]
+          .filter(list => newLists[i].indexOf(list) == -1);
+      }
+    }
+
     this.updateProviderURLs();
     this.registerTables();
+    if (obsoleteLists) {
+      this.unregisterTables(obsoleteLists);
+    }
 
     // XXX The listManager backend gets confused if this is called before the
     // lists are registered. So only call it here when a pref changes, and not
     // when doing initialization. I expect to refactor this later, so pardon the hack.
     if (this.initialized) {
       this.controlUpdateChecking();
     }
   },

--- a/toolkit/components/url-classifier/nsIUrlListManager.idl
+++ b/toolkit/components/url-classifier/nsIUrlListManager.idl
@@ -35,16 +35,21 @@ interface nsIUrlListManager : nsISupport
      * @param gethashUrl The URL from which to fetch hash completions.
      */
     boolean registerTable(in ACString tableName,
                           in ACString providerName,
                           in ACString updateUrl,
                           in ACString gethashUrl);
 
     /**
+     * Unregister table from the list
+     */
+    void unregisterTable(in ACString tableName);
+
+    /**
      * Turn on update checking for a table. I.e., during the next server
      * check, download updates for this table.
      */
     void enableUpdate(in ACString tableName);
 
     /**
      * Turn off update checking for a table.
      */

--- a/toolkit/components/url-classifier/nsUrlClassifierListManager.js
+++ b/toolkit/components/url-classifier/nsUrlClassifierListManager.js
@@ -104,16 +104,34 @@ PROT_ListManager.prototype.registerTable
                                60 * 60 * 1000 /* request time, 60 min */);
   }
   this.needsUpdate_[updateUrl][tableName] = false;
 
   return true;
 }
 
 /**
+ * Unregister a table table from list
+ */
+PROT_ListManager.prototype.unregisterTable = function(tableName) {
+  log("unregistering " + tableName);
+  var table = this.tablesData[tableName];
+  if (table) {
+    if (!this.updatesNeeded_(table.updateUrl) &&
+        this.updateCheckers_[table.updateUrl]) {
+      this.updateCheckers_[table.updateUrl].cancel();
+      this.updateCheckers_[table.updateUrl] = null;
+    }
+    delete this.needsUpdate_[table.updateUrl][tableName];
+  }
+  delete this.tablesData[tableName];
+
+}
+
+/**
  * Delete all of our data tables which seem to leak otherwise.
  * Remove observers
  */
 PROT_ListManager.prototype.shutdown_ = function() {
   this.stopUpdateCheckers();
   for (var name in this.tablesData) {
     delete this.tablesData[name];
   }

--- a/toolkit/components/url-classifier/tests/mochitest/chrome.ini
+++ b/toolkit/components/url-classifier/tests/mochitest/chrome.ini
@@ -22,11 +22,12 @@ tags = trackingprotection
 tags = trackingprotection
 [test_trackingprotection_bug1157081.html]
 tags = trackingprotection
 [test_trackingprotection_whitelist.html]
 tags = trackingprotection
 [test_safebrowsing_bug1272239.html]
 [test_donottrack.html]
 [test_classifier_changetablepref.html]
+[test_classifier_changetablepref_bug1395411.html]
 [test_reporturl.html]
 [test_trackingprotection_bug1312515.html]
 [test_advisory_link.html]

new file mode 100644
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/mochitest/test_classifier_changetablepref_bug1395411.html
@@ -0,0 +1,74 @@
+<!DOCTYPE HTML>
+<!-- Any copyright is dedicated to the Public Domain.
+     http://creativecommons.org/publicdomain/zero/1.0/ -->
+<html>
+<head>
+  <title>Bug 1395411 - Changing the urlclassifier.*Table prefs doesn't remove them from the update checker.</title>
+  <script type="text/javascript" src="chrome://mochikit/content/tests/SimpleTest/SimpleTest.js"></script>
+  <script type="text/javascript" src="classifierHelper.js"></script>
+  <link rel="stylesheet" type="text/css" href="chrome://mochikit/content/tests/SimpleTest/test.css">
+</head>
+
+<body>
+<p id="display"></p>
+<div id="content" style="display: none">
+</div>
+<pre id="test">
+
+<script class="testbody" type="text/javascript">
+/* import-globals-from classifierHelper.js */
+var Cc = SpecialPowers.Cc;
+var Ci = SpecialPowers.Ci;
+
+const testTableV2 = "mochi1-phish-simple";
+const testTableV4 = "mochi1-phish-proto";
+const UPDATE_URL_V2 = "http://mochi.test:8888/tests/toolkit/components/url-classifier/dummyV2";
+const UPDATE_URL_V4 = "http://mochi.test:8888/tests/toolkit/components/url-classifier/dummyV4";
+
+let listmanager = Cc["@mozilla.org/url-classifier/listmanager;1"].
+                    getService(Ci.nsIUrlListManager);
+
+let pushPrefs = (...p) => SpecialPowers.pushPrefEnv({set: p});
+
+SpecialPowers.pushPrefEnv(
+  {"set": [["browser.safebrowsing.phishing.enabled", true],
+           ["browser.safebrowsing.provider.mozilla.lists", testTableV2],
+           ["browser.safebrowsing.provider.mozilla4.lists", testTableV4],
+           ["browser.safebrowsing.provider.mozilla4.updateURL", UPDATE_URL_V4],
+           ["browser.safebrowsing.provider.mozilla.updateURL", UPDATE_URL_V2]]},
+  runTest);
+
+function runTest() {
+  (async function() {
+    await classifierHelper.waitForInit();
+
+    await pushPrefs(["urlclassifier.phishTable", testTableV2 + "," + testTableV4]);
+    is(listmanager.getUpdateUrl(testTableV4), UPDATE_URL_V4, "Correct update url v4");
+    is(listmanager.getUpdateUrl(testTableV2), UPDATE_URL_V2, "Correct update url v2");
+
+    await pushPrefs(["urlclassifier.phishTable", testTableV2]);
+    is(listmanager.getUpdateUrl(testTableV4), "", "Correct empty update url v4");
+    is(listmanager.getUpdateUrl(testTableV2), UPDATE_URL_V2, "Correct update url v2");
+
+    await pushPrefs(["urlclassifier.phishTable", testTableV4]);
+    is(listmanager.getUpdateUrl(testTableV4), UPDATE_URL_V4, "Correct update url v4");
+    is(listmanager.getUpdateUrl(testTableV2), "", "Correct empty update url v2");
+
+    await pushPrefs(["urlclassifier.phishTable", ""]);
+    is(listmanager.getUpdateUrl(testTableV4), "", "Correct empty update url v4");
+    is(listmanager.getUpdateUrl(testTableV2), "", "Correct empty update url v2");
+
+    await classifierHelper._cleanup();
+
+    SimpleTest.finish();
+  })();
+}
+
+SimpleTest.waitForExplicitFinish();
+
+</script>
+</pre>
+<iframe id="testFrame" width="100%" height="100%" onload=""></iframe>
+</body>
+</html>
+