--- a/browser/extensions/doh-rollout/background.js
+++ b/browser/extensions/doh-rollout/background.js
@@ -645,11 +645,18 @@ const setup = {
         );
       } catch (e) {
         // Captive Portal Service is disabled.
       }
     }
   });
 
   if (await rollout.getSetting(DOH_ENABLED_PREF, false)) {
-    setup.start();
+    await setup.start();
+  } else if (
+    (await rollout.getSetting(DOH_DONE_FIRST_RUN_PREF, false)) &&
+    (await stateManager.shouldRunHeuristics())
+  ) {
+    // We previously had turned on DoH, and now after a restart we've been
+    // rolled back. Reset TRR mode.
+    await stateManager.setState("disabled");
   }
 })();

--- a/browser/extensions/doh-rollout/test/browser/browser_rollback.js
+++ b/browser/extensions/doh-rollout/test/browser/browser_rollback.js
@@ -1,10 +1,12 @@
 "use strict";
 
+requestLongerTimeout(2);
+
 add_task(setup);
 
 add_task(async function testRollback() {
   // Set up a passing environment and enable DoH.
   setPassingHeuristics();
   let promise = waitForDoorhanger();
   Preferences.set(prefs.DOH_ENABLED_PREF, true);
 
@@ -61,16 +63,17 @@ add_task(async function testRollback() {
   simulateNetworkChange();
   await ensureNoTRRModeChange(0);
   await checkHeuristicsTelemetry("disable_doh", "netchange");
 
   // Rollback!
   setPassingHeuristics();
   Preferences.reset(prefs.DOH_ENABLED_PREF);
   await ensureTRRMode(0);
+  await ensureNoHeuristicsTelemetry();
   simulateNetworkChange();
   await ensureNoTRRModeChange(0);
   await ensureNoHeuristicsTelemetry();
 
   // Re-enable.
   Preferences.set(prefs.DOH_ENABLED_PREF, true);
 
   await ensureTRRMode(2);
@@ -79,17 +82,18 @@ add_task(async function testRollback() {
   // Change the environment to failing and simulate a network change.
   setFailingHeuristics();
   simulateNetworkChange();
   await ensureTRRMode(0);
   await checkHeuristicsTelemetry("disable_doh", "netchange");
 
   // Rollback again for good measure! This time with failing heuristics.
   Preferences.reset(prefs.DOH_ENABLED_PREF);
-  await ensureTRRMode(0);
+  await ensureNoTRRModeChange(0);
+  await ensureNoHeuristicsTelemetry();
   simulateNetworkChange();
   await ensureNoTRRModeChange(0);
   await ensureNoHeuristicsTelemetry();
 
   // Re-enable.
   Preferences.set(prefs.DOH_ENABLED_PREF, true);
 
   await ensureNoTRRModeChange(0);
@@ -99,12 +103,33 @@ add_task(async function testRollback() {
   setPassingHeuristics();
   simulateNetworkChange();
   await ensureTRRMode(2);
   await checkHeuristicsTelemetry("enable_doh", "netchange");
 
   // Rollback again, this time with TRR mode set to 2 prior to doing so.
   Preferences.reset(prefs.DOH_ENABLED_PREF);
   await ensureTRRMode(0);
+  await ensureNoHeuristicsTelemetry();
+  simulateNetworkChange();
+  await ensureNoTRRModeChange(0);
+  await ensureNoHeuristicsTelemetry();
+
+  // Re-enable.
+  Preferences.set(prefs.DOH_ENABLED_PREF, true);
+
+  await ensureTRRMode(2);
+  await checkHeuristicsTelemetry("enable_doh", "startup");
+  simulateNetworkChange();
+  await ensureNoTRRModeChange(2);
+  await checkHeuristicsTelemetry("enable_doh", "netchange");
+
+  // Rollback again. This time, disable the add-on first to ensure it reacts
+  // correctly at startup.
+  await disableAddon();
+  Preferences.reset(prefs.DOH_ENABLED_PREF);
+  await enableAddon();
+  await ensureTRRMode(0);
+  await ensureNoHeuristicsTelemetry();
   simulateNetworkChange();
   await ensureNoTRRModeChange(0);
   await ensureNoHeuristicsTelemetry();
 });

--- a/browser/extensions/doh-rollout/test/browser/head.js
+++ b/browser/extensions/doh-rollout/test/browser/head.js
@@ -125,16 +125,26 @@ function setFailingHeuristics() {
   Preferences.set(prefs.MOCK_HEURISTICS_PREF, fakeFailingHeuristics);
 }
 
 async function restartAddon() {
   let addon = await AddonManager.getAddonByID(ADDON_ID);
   await addon.reload();
 }
 
+async function disableAddon() {
+  let addon = await AddonManager.getAddonByID(ADDON_ID);
+  await addon.disable({ allowSystemAddons: true });
+}
+
+async function enableAddon() {
+  let addon = await AddonManager.getAddonByID(ADDON_ID);
+  await addon.enable({ allowSystemAddons: true });
+}
+
 async function resetPrefsAndRestartAddon() {
   let addon = await AddonManager.getAddonByID(ADDON_ID);
   await addon.disable({ allowSystemAddons: true });
   Preferences.reset(Object.values(prefs));
   await addon.enable({ allowSystemAddons: true });
 }
 
 async function waitForDoorhanger() {