diff --git a/update_attempter_android.cc b/update_attempter_android.cc
index 680bbaf..a8a5953 100644
--- a/update_attempter_android.cc
+++ b/update_attempter_android.cc
@@ -157,6 +157,7 @@
   } else {
     SetStatusAndNotify(UpdateStatus::IDLE);
     UpdatePrefsAndReportUpdateMetricsOnReboot();
+    ScheduleCleanupPreviousUpdate();
   }
 }
 
@@ -502,6 +503,11 @@
                                             ErrorCode code) {
   LOG(INFO) << "Processing Done.";
 
+  if (status_ == UpdateStatus::CLEANUP_PREVIOUS_UPDATE) {
+    TerminateUpdateAndNotify(code);
+    return;
+  }
+
   switch (code) {
     case ErrorCode::kSuccess:
       // Update succeeded.
@@ -625,6 +631,12 @@
     return;
   }
 
+  if (status_ == UpdateStatus::CLEANUP_PREVIOUS_UPDATE) {
+    LOG(INFO) << "Terminating cleanup previous update.";
+    SetStatusAndNotify(UpdateStatus::IDLE);
+    return;
+  }
+
   boot_control_->GetDynamicPartitionControl()->Cleanup();
 
   download_progress_ = 0;
@@ -944,4 +956,24 @@
   return static_cast<int32_t>(error_code);
 }
 
+void UpdateAttempterAndroid::ScheduleCleanupPreviousUpdate() {
+  // If a previous CleanupSuccessfulUpdate call has not finished, or an update
+  // is in progress, skip enqueueing the action.
+  if (processor_->IsRunning()) {
+    LOG(INFO) << "Already processing an update. CleanupPreviousUpdate should "
+              << "be done when the current update finishes.";
+    return;
+  }
+  LOG(INFO) << "Scheduling CleanupPreviousUpdateAction.";
+  auto action =
+      boot_control_->GetDynamicPartitionControl()
+          ->GetCleanupPreviousUpdateAction(boot_control_, prefs_, this);
+  processor_->EnqueueAction(std::move(action));
+  processor_->set_delegate(this);
+  SetStatusAndNotify(UpdateStatus::CLEANUP_PREVIOUS_UPDATE);
+  processor_->StartProcessing();
+}
+
+void UpdateAttempterAndroid::OnCleanupProgressUpdate(double progress) {}
+
 }  // namespace chromeos_update_engine