diff --git a/constants.cc b/constants.cc
index 0f425d7..e4aa199 100644
--- a/constants.cc
+++ b/constants.cc
@@ -34,6 +34,7 @@
 const char kPrefsPayloadAttemptNumber[] = "payload-attempt-number";
 const char kPrefsPreviousVersion[] = "previous-version";
 const char kPrefsResumedUpdateFailures[] = "resumed-update-failures";
+const char kPrefsSystemUpdatedMarker[] = "system-updated-marker";
 const char kPrefsTotalBytesDownloaded[] = "total-bytes-downloaded";
 const char kPrefsUpdateCheckCount[] = "update-check-count";
 const char kPrefsUpdateCheckResponseHash[] = "update-check-response-hash";
diff --git a/constants.h b/constants.h
index 4bd9685..f2dfc5a 100644
--- a/constants.h
+++ b/constants.h
@@ -37,6 +37,7 @@
 extern const char kPrefsPayloadAttemptNumber[];
 extern const char kPrefsPreviousVersion[];
 extern const char kPrefsResumedUpdateFailures[];
+extern const char kPrefsSystemUpdatedMarker[];
 extern const char kPrefsTotalBytesDownloaded[];
 extern const char kPrefsUpdateCheckCount[];
 extern const char kPrefsUpdateCheckResponseHash[];
diff --git a/main.cc b/main.cc
index 47fb934..b045793 100644
--- a/main.cc
+++ b/main.cc
@@ -52,6 +52,11 @@
   return FALSE;  // Don't call this callback again
 }
 
+gboolean UpdateEngineStarted(gpointer user_data) {
+  reinterpret_cast<UpdateAttempter*>(user_data)->UpdateEngineStarted();
+  return FALSE; // Remove idle source (e.g. don't do the callback again)
+}
+
 namespace {
 
 void SetupDbusService(UpdateEngineService* service) {
@@ -205,6 +210,9 @@
   // state on crashes.
   g_idle_add(&chromeos_update_engine::BroadcastStatus, update_attempter);
 
+  // Run the UpdateEngineStarted() method on |update_attempter|.
+  g_idle_add(&chromeos_update_engine::UpdateEngineStarted, update_attempter);
+
   // Run the main loop until exit time:
   g_main_loop_run(loop);
 
diff --git a/mock_payload_state.h b/mock_payload_state.h
index 8d1edf5..3dcf03c 100644
--- a/mock_payload_state.h
+++ b/mock_payload_state.h
@@ -26,6 +26,7 @@
   MOCK_METHOD0(UpdateSucceeded, void());
   MOCK_METHOD1(UpdateFailed, void(ErrorCode error));
   MOCK_METHOD0(ShouldBackoffDownload, bool());
+  MOCK_METHOD0(UpdateEngineStarted, void());
 
   // Getters.
   MOCK_METHOD0(GetResponseSignature, std::string());
diff --git a/payload_state.cc b/payload_state.cc
index b804822..c8647dd 100644
--- a/payload_state.cc
+++ b/payload_state.cc
@@ -158,6 +158,8 @@
   // Reset the number of responses seen since it counts from the last
   // successful update, e.g. now.
   SetNumResponsesSeen(0);
+
+  CreateSystemUpdatedMarkerFile();
 }
 
 void PayloadState::UpdateFailed(ErrorCode error) {
@@ -941,4 +943,43 @@
             << "out of " << response_.payload_urls.size() << " URLs supplied";
 }
 
+void PayloadState::CreateSystemUpdatedMarkerFile() {
+  CHECK(prefs_);
+  int64_t value = system_state_->clock()->GetWallclockTime().ToInternalValue();
+  prefs_->SetInt64(kPrefsSystemUpdatedMarker, value);
+}
+
+void PayloadState::BootedIntoUpdate(TimeDelta time_to_reboot) {
+  // Send |time_to_reboot| as a UMA stat.
+  string metric = "Installer.TimeToRebootMinutes";
+  system_state_->metrics_lib()->SendToUMA(metric,
+                                          time_to_reboot.InMinutes(),
+                                          0,        // min: 0 minute
+                                          30*24*60, // max: 1 month (approx)
+                                          kNumDefaultUmaBuckets);
+  LOG(INFO) << "Uploading " << utils::FormatTimeDelta(time_to_reboot)
+            << " for metric " <<  metric;
+}
+
+void PayloadState::UpdateEngineStarted() {
+  // Figure out if we just booted into a new update
+  if (prefs_->Exists(kPrefsSystemUpdatedMarker)) {
+    int64_t stored_value;
+    if (prefs_->GetInt64(kPrefsSystemUpdatedMarker, &stored_value)) {
+      Time system_updated_at = Time::FromInternalValue(stored_value);
+      if (!system_updated_at.is_null()) {
+        TimeDelta time_to_reboot =
+            system_state_->clock()->GetWallclockTime() - system_updated_at;
+        if (time_to_reboot.ToInternalValue() < 0) {
+          LOG(ERROR) << "time_to_reboot is negative - system_updated_at: "
+                     << utils::ToString(system_updated_at);
+        } else {
+          BootedIntoUpdate(time_to_reboot);
+        }
+      }
+    }
+    prefs_->Delete(kPrefsSystemUpdatedMarker);
+  }
+}
+
 }  // namespace chromeos_update_engine
diff --git a/payload_state.h b/payload_state.h
index f8a2d0c..7c0d0d3 100644
--- a/payload_state.h
+++ b/payload_state.h
@@ -85,6 +85,8 @@
     return num_reboots_;
   }
 
+  virtual void UpdateEngineStarted();
+
  private:
   // Increments the payload attempt number which governs the backoff behavior
   // at the time of the next update check.
@@ -280,6 +282,17 @@
   // increments num_reboots.
   void UpdateNumReboots();
 
+  // Writes the current wall-clock time to the kPrefsSystemUpdatedMarker
+  // state variable.
+  void CreateSystemUpdatedMarkerFile();
+
+  // Called at program startup if the device booted into a new update.
+  // The |time_to_reboot| parameter contains the (wall-clock) duration
+  // from when the update successfully completed (the value written
+  // into the kPrefsSystemUpdatedMarker state variable) until the device
+  // was booted into the update (current wall-clock time).
+  void BootedIntoUpdate(base::TimeDelta time_to_reboot);
+
   // Interface object with which we read/write persisted state. This must
   // be set by calling the Initialize method before calling any other method.
   PrefsInterface* prefs_;
diff --git a/payload_state_interface.h b/payload_state_interface.h
index 0cfb969..a7129c9 100644
--- a/payload_state_interface.h
+++ b/payload_state_interface.h
@@ -109,6 +109,9 @@
 
   // Returns the reboot count for this update attempt.
   virtual uint32_t GetNumReboots() = 0;
+
+  // Called at update_engine startup to do various house-keeping.
+  virtual void UpdateEngineStarted() = 0;
  };
 
 }  // namespace chromeos_update_engine
diff --git a/payload_state_unittest.cc b/payload_state_unittest.cc
index 13052ef..c935178 100644
--- a/payload_state_unittest.cc
+++ b/payload_state_unittest.cc
@@ -851,6 +851,56 @@
   EXPECT_TRUE(utils::RecursiveUnlinkDir(temp_dir));
 }
 
+TEST(PayloadStateTest, RebootAfterSuccessfulUpdateTest) {
+  OmahaResponse response;
+  PayloadState payload_state;
+  MockSystemState mock_system_state;
+  FakeClock fake_clock;
+  Prefs prefs;
+  string temp_dir;
+
+  // Set the clock to a well-known time (t = 30 seconds).
+  fake_clock.SetWallclockTime(Time::FromInternalValue(
+      30 * Time::kMicrosecondsPerSecond));
+
+  // We need persistent preferences for this test
+  EXPECT_TRUE(utils::MakeTempDirectory(
+      "/tmp/RebootAfterSuccessfulUpdateTest.XXXXXX", &temp_dir));
+  prefs.Init(FilePath(temp_dir));
+
+  mock_system_state.set_clock(&fake_clock);
+  mock_system_state.set_prefs(&prefs);
+  EXPECT_TRUE(payload_state.Initialize(&mock_system_state));
+
+  // Make the update succeed.
+  SetupPayloadStateWith2Urls("Hash8593", true, &payload_state, &response);
+  payload_state.UpdateSucceeded();
+
+  // Check that the marker was written.
+  EXPECT_TRUE(prefs.Exists(kPrefsSystemUpdatedMarker));
+
+  // Now simulate a reboot and set the wallclock time to a later point
+  // (t = 500 seconds). We do this by using a new PayloadState object
+  // and checking that it emits the right UMA metric with the right
+  // value.
+  fake_clock.SetWallclockTime(Time::FromInternalValue(
+      500 * Time::kMicrosecondsPerSecond));
+  PayloadState payload_state2;
+  EXPECT_TRUE(payload_state2.Initialize(&mock_system_state));
+
+  // Expect 500 - 30 seconds = 470 seconds ~= 7 min 50 sec
+  EXPECT_CALL(*mock_system_state.mock_metrics_lib(), SendToUMA(
+      "Installer.TimeToRebootMinutes",
+      7, _, _, _));
+
+  payload_state2.UpdateEngineStarted();
+
+  // Check that the marker was nuked.
+  EXPECT_FALSE(prefs.Exists(kPrefsSystemUpdatedMarker));
+
+  EXPECT_TRUE(utils::RecursiveUnlinkDir(temp_dir));
+}
+
 TEST(PayloadStateTest, CandidateUrlsComputedCorrectly) {
   OmahaResponse response;
   MockSystemState mock_system_state;
diff --git a/update_attempter.cc b/update_attempter.cc
index 3a6988e..799cd20 100644
--- a/update_attempter.cc
+++ b/update_attempter.cc
@@ -1177,4 +1177,8 @@
   return false;
 }
 
+void UpdateAttempter::UpdateEngineStarted() {
+  system_state_->payload_state()->UpdateEngineStarted();
+}
+
 }  // namespace chromeos_update_engine
diff --git a/update_attempter.h b/update_attempter.h
index d33d69e..a9dadf0 100644
--- a/update_attempter.h
+++ b/update_attempter.h
@@ -171,6 +171,9 @@
   // |cancel_reason| is untouched.
   bool ShouldCancel(ErrorCode* cancel_reason);
 
+  // Called at update_engine startup to do various house-keeping.
+  void UpdateEngineStarted();
+
  private:
   // Update server URL for automated lab test.
   static const char* const kTestUpdateUrl;