diff --git a/client_library/include/update_engine/update_status.h b/client_library/include/update_engine/update_status.h
index 5a3dccf..6490e27 100644
--- a/client_library/include/update_engine/update_status.h
+++ b/client_library/include/update_engine/update_status.h
@@ -41,6 +41,7 @@
   // Broadcast this state when an update aborts because user preferences do not
   // allow updates, e.g. over cellular network.
   NEED_PERMISSION_TO_UPDATE = 10,
+  CLEANUP_PREVIOUS_UPDATE = 11,
 };
 
 // Enum of bit-wise flags for controlling how updates are attempted.
diff --git a/common/action.h b/common/action.h
index 9e2f5ff..c93e73c 100644
--- a/common/action.h
+++ b/common/action.h
@@ -222,6 +222,16 @@
       out_pipe_;
 };
 
+// An action that does nothing and completes with kSuccess immediately.
+class NoOpAction : public AbstractAction {
+ public:
+  ~NoOpAction() override {}
+  void PerformAction() override {
+    processor_->ActionComplete(this, ErrorCode::kSuccess);
+  }
+  std::string Type() const override { return "NoOpAction"; }
+};
+
 };  // namespace chromeos_update_engine
 
 #endif  // UPDATE_ENGINE_COMMON_ACTION_H_
diff --git a/common/dynamic_partition_control_interface.h b/common/dynamic_partition_control_interface.h
index 48cd9be..8de9d76 100644
--- a/common/dynamic_partition_control_interface.h
+++ b/common/dynamic_partition_control_interface.h
@@ -22,6 +22,8 @@
 #include <memory>
 #include <string>
 
+#include "update_engine/common/action.h"
+#include "update_engine/common/cleanup_previous_update_action_delegate.h"
 #include "update_engine/common/error_code.h"
 #include "update_engine/update_metadata.pb.h"
 
@@ -38,6 +40,9 @@
   Value value_;
 };
 
+class BootControlInterface;
+class PrefsInterface;
+
 class DynamicPartitionControlInterface {
  public:
   virtual ~DynamicPartitionControlInterface() = default;
@@ -79,6 +84,7 @@
   // this function to indicate writes to new partitions are done.
   virtual bool FinishUpdate() = 0;
 
+  // Deprecated. Use GetCleanupPreviousUpdateAction instead.
   // Before applying the next update, call this function to clean up previous
   // update files. This function blocks until delta files are merged into
   // current OS partitions and finished cleaning up.
@@ -86,6 +92,20 @@
   // - If any error, but caller should retry after reboot, return kError.
   // - If any irrecoverable failures, return kDeviceCorrupted.
   virtual ErrorCode CleanupSuccessfulUpdate() = 0;
+
+  // Get an action to clean up previous update.
+  // Return NoOpAction on non-Virtual A/B devices.
+  // Before applying the next update, run this action to clean up previous
+  // update files. This function blocks until delta files are merged into
+  // current OS partitions and finished cleaning up.
+  // - If successful, action completes with kSuccess.
+  // - If any error, but caller should retry after reboot, action completes with
+  //   kError.
+  // - If any irrecoverable failures, action completes with kDeviceCorrupted.
+  virtual std::unique_ptr<AbstractAction> GetCleanupPreviousUpdateAction(
+      BootControlInterface* boot_control,
+      PrefsInterface* prefs,
+      CleanupPreviousUpdateActionDelegateInterface* delegate) = 0;
 };
 
 }  // namespace chromeos_update_engine
diff --git a/common/dynamic_partition_control_stub.cc b/common/dynamic_partition_control_stub.cc
index cc36c5c..70d6768 100644
--- a/common/dynamic_partition_control_stub.cc
+++ b/common/dynamic_partition_control_stub.cc
@@ -16,6 +16,7 @@
 
 #include <stdint.h>
 
+#include <memory>
 #include <string>
 
 #include <base/logging.h>
@@ -56,4 +57,12 @@
   return ErrorCode::kError;
 }
 
+std::unique_ptr<AbstractAction>
+DynamicPartitionControlStub::GetCleanupPreviousUpdateAction(
+    BootControlInterface* boot_control,
+    PrefsInterface* prefs,
+    CleanupPreviousUpdateActionDelegateInterface* delegate) {
+  return std::make_unique<NoOpAction>();
+}
+
 }  // namespace chromeos_update_engine
diff --git a/common/dynamic_partition_control_stub.h b/common/dynamic_partition_control_stub.h
index 02575a1..92e9922 100644
--- a/common/dynamic_partition_control_stub.h
+++ b/common/dynamic_partition_control_stub.h
@@ -19,6 +19,7 @@
 
 #include <stdint.h>
 
+#include <memory>
 #include <string>
 
 #include "update_engine/common/dynamic_partition_control_interface.h"
@@ -40,6 +41,10 @@
 
   bool FinishUpdate() override;
   ErrorCode CleanupSuccessfulUpdate() override;
+  std::unique_ptr<AbstractAction> GetCleanupPreviousUpdateAction(
+      BootControlInterface* boot_control,
+      PrefsInterface* prefs,
+      CleanupPreviousUpdateActionDelegateInterface* delegate) override;
 };
 
 }  // namespace chromeos_update_engine
diff --git a/dynamic_partition_control_android.cc b/dynamic_partition_control_android.cc
index 938a75b..84c2f78 100644
--- a/dynamic_partition_control_android.cc
+++ b/dynamic_partition_control_android.cc
@@ -35,6 +35,7 @@
 #include <libdm/dm.h>
 #include <libsnapshot/snapshot.h>
 
+#include "update_engine/cleanup_previous_update_action.h"
 #include "update_engine/common/boot_control_interface.h"
 #include "update_engine/common/utils.h"
 #include "update_engine/dynamic_partition_utils.h"
@@ -786,4 +787,16 @@
   return true;
 }
 
+std::unique_ptr<AbstractAction>
+DynamicPartitionControlAndroid::GetCleanupPreviousUpdateAction(
+    BootControlInterface* boot_control,
+    PrefsInterface* prefs,
+    CleanupPreviousUpdateActionDelegateInterface* delegate) {
+  if (!GetVirtualAbFeatureFlag().IsEnabled()) {
+    return std::make_unique<NoOpAction>();
+  }
+  return std::make_unique<CleanupPreviousUpdateAction>(
+      prefs, boot_control, snapshot_.get(), delegate);
+}
+
 }  // namespace chromeos_update_engine
diff --git a/dynamic_partition_control_android.h b/dynamic_partition_control_android.h
index e7ae26b..aff0296 100644
--- a/dynamic_partition_control_android.h
+++ b/dynamic_partition_control_android.h
@@ -46,6 +46,10 @@
                                   uint64_t* required_size) override;
   bool FinishUpdate() override;
   ErrorCode CleanupSuccessfulUpdate() override;
+  std::unique_ptr<AbstractAction> GetCleanupPreviousUpdateAction(
+      BootControlInterface* boot_control,
+      PrefsInterface* prefs,
+      CleanupPreviousUpdateActionDelegateInterface* delegate) override;
 
   // Return the device for partition |partition_name| at slot |slot|.
   // |current_slot| should be set to the current active slot.
diff --git a/mock_dynamic_partition_control.h b/mock_dynamic_partition_control.h
index 1237d76..b3e0c24 100644
--- a/mock_dynamic_partition_control.h
+++ b/mock_dynamic_partition_control.h
@@ -44,6 +44,11 @@
   MOCK_METHOD0(GetVirtualAbFeatureFlag, FeatureFlag());
   MOCK_METHOD0(FinishUpdate, bool());
   MOCK_METHOD0(CleanupSuccessfulUpdate, ErrorCode());
+  MOCK_METHOD3(GetCleanupPreviousUpdateAction,
+               std::unique_ptr<AbstractAction>(
+                   BootControlInterface*,
+                   PrefsInterface*,
+                   CleanupPreviousUpdateActionDelegateInterface*));
 };
 
 class MockDynamicPartitionControlAndroid
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
diff --git a/update_attempter_android.h b/update_attempter_android.h
index c301e64..106e117 100644
--- a/update_attempter_android.h
+++ b/update_attempter_android.h
@@ -47,7 +47,8 @@
     : public ServiceDelegateAndroidInterface,
       public ActionProcessorDelegate,
       public DownloadActionDelegate,
-      public PostinstallRunnerAction::DelegateInterface {
+      public PostinstallRunnerAction::DelegateInterface,
+      public CleanupPreviousUpdateActionDelegateInterface {
  public:
   using UpdateStatus = update_engine::UpdateStatus;
 
@@ -101,6 +102,9 @@
   // PostinstallRunnerAction::DelegateInterface
   void ProgressUpdate(double progress) override;
 
+  // CleanupPreviousUpdateActionDelegateInterface
+  void OnCleanupProgressUpdate(double progress) override;
+
  private:
   friend class UpdateAttempterAndroidTest;
 
@@ -177,6 +181,9 @@
                                          DeltaArchiveManifest* manifest,
                                          brillo::ErrorPtr* error);
 
+  // Enqueue and run a CleanupPreviousUpdateAction.
+  void ScheduleCleanupPreviousUpdate();
+
   DaemonStateInterface* daemon_state_;
 
   // DaemonStateAndroid pointers.
diff --git a/update_status_utils.cc b/update_status_utils.cc
index cbc4f14..11fd299 100644
--- a/update_status_utils.cc
+++ b/update_status_utils.cc
@@ -46,6 +46,8 @@
       return update_engine::kUpdateStatusAttemptingRollback;
     case UpdateStatus::DISABLED:
       return update_engine::kUpdateStatusDisabled;
+    case UpdateStatus::CLEANUP_PREVIOUS_UPDATE:
+      return update_engine::kUpdateStatusCleanupPreviousUpdate;
   }
 
   NOTREACHED();
@@ -86,6 +88,9 @@
   } else if (s == update_engine::kUpdateStatusDisabled) {
     *status = UpdateStatus::DISABLED;
     return true;
+  } else if (s == update_engine::kUpdateStatusCleanupPreviousUpdate) {
+    *status = UpdateStatus::CLEANUP_PREVIOUS_UPDATE;
+    return true;
   }
   return false;
 }