diff --git a/src/commands/command_queue.cc b/src/commands/command_queue.cc
index cdb251f..f0d2228 100644
--- a/src/commands/command_queue.cc
+++ b/src/commands/command_queue.cc
@@ -18,6 +18,10 @@
 }
 }
 
+CommandQueue::CommandQueue(provider::TaskRunner* task_runner,
+                           base::Clock* clock)
+    : task_runner_{task_runner}, clock_{clock} {}
+
 void CommandQueue::AddCommandAddedCallback(const CommandCallback& callback) {
   on_command_added_.push_back(callback);
   // Send all pre-existed commands.
@@ -84,18 +88,19 @@
     it_handler->second.Run(pair.first->second);
   else if (!default_command_callback_.is_null())
     default_command_callback_.Run(pair.first->second);
-
-  Cleanup();
 }
 
 void CommandQueue::RemoveLater(const std::string& id) {
   auto p = map_.find(id);
   if (p == map_.end())
     return;
-  remove_queue_.push(std::make_pair(
-      base::Time::Now() + base::TimeDelta::FromMinutes(kRemoveCommandDelayMin),
-      id));
-  Cleanup();
+  auto remove_delay = base::TimeDelta::FromMinutes(kRemoveCommandDelayMin);
+  remove_queue_.push(std::make_pair(clock_->Now() + remove_delay, id));
+  if (remove_queue_.size() == 1) {
+    // The queue was empty, this is the first command to be removed, schedule
+    // a clean-up task.
+    ScheduleCleanup(remove_delay);
+  }
 }
 
 bool CommandQueue::Remove(const std::string& id) {
@@ -110,19 +115,26 @@
   return true;
 }
 
-void CommandQueue::Cleanup() {
-  while (!remove_queue_.empty() && remove_queue_.front().first < Now()) {
-    Remove(remove_queue_.front().second);
+void CommandQueue::Cleanup(const base::Time& cutoff_time) {
+  while (!remove_queue_.empty() && remove_queue_.top().first <= cutoff_time) {
+    Remove(remove_queue_.top().second);
     remove_queue_.pop();
   }
 }
 
-void CommandQueue::SetNowForTest(base::Time now) {
-  test_now_ = now;
+void CommandQueue::ScheduleCleanup(base::TimeDelta delay) {
+  task_runner_->PostDelayedTask(
+      FROM_HERE,
+      base::Bind(&CommandQueue::PerformScheduledCleanup,
+                 weak_ptr_factory_.GetWeakPtr()),
+      delay);
 }
 
-base::Time CommandQueue::Now() const {
-  return test_now_.is_null() ? base::Time::Now() : test_now_;
+void CommandQueue::PerformScheduledCleanup() {
+  base::Time now = clock_->Now();
+  Cleanup(now);
+  if (!remove_queue_.empty())
+    ScheduleCleanup(remove_queue_.top().first - now);
 }
 
 CommandInstance* CommandQueue::Find(const std::string& id) const {
diff --git a/src/commands/command_queue.h b/src/commands/command_queue.h
index 01839d8..a092c12 100644
--- a/src/commands/command_queue.h
+++ b/src/commands/command_queue.h
@@ -14,8 +14,10 @@
 
 #include <base/callback.h>
 #include <base/macros.h>
+#include <base/time/default_clock.h>
 #include <base/time/time.h>
 #include <weave/device.h>
+#include <weave/provider/task_runner.h>
 
 #include "src/commands/command_instance.h"
 
@@ -23,7 +25,7 @@
 
 class CommandQueue final {
  public:
-  CommandQueue() = default;
+  CommandQueue(provider::TaskRunner* task_runner, base::Clock* clock);
 
   // TODO: Remove AddCommandAddedCallback and AddCommandRemovedCallback.
   using CommandCallback = base::Callback<void(Command* command)>;
@@ -64,23 +66,29 @@
   // Removes a command identified by |id| from the queue.
   bool Remove(const std::string& id);
 
-  // Removes old commands selected with DelayedRemove.
-  void Cleanup();
+  // Removes old commands scheduled by RemoveLater() to be deleted after
+  // |cutoff_time|.
+  void Cleanup(const base::Time& cutoff_time);
 
-  // Overrides CommandQueue::Now() for tests.
-  void SetNowForTest(base::Time now);
+  // Schedule a cleanup task to be run after the specified |delay|.
+  void ScheduleCleanup(base::TimeDelta delay);
 
-  // Returns current time.
-  base::Time Now() const;
+  // Perform removal of scheduled commands (by calling Cleanup()) and scheduling
+  // another cleanup task if the removal queue is still not empty.
+  void PerformScheduledCleanup();
 
-  // Overridden value to be returned from Now().
-  base::Time test_now_;
+  provider::TaskRunner* task_runner_{nullptr};
+  base::Clock* clock_{nullptr};
 
   // ID-to-CommandInstance map.
   std::map<std::string, std::shared_ptr<CommandInstance>> map_;
 
-  // Queue of commands to be removed.
-  std::queue<std::pair<base::Time, std::string>> remove_queue_;
+  // Queue of commands to be removed, keeps them sorted by the timestamp
+  // (earliest first). This is done to tolerate system clock changes.
+  template <typename T>
+  using InversePriorityQueue =
+      std::priority_queue<T, std::vector<T>, std::greater<T>>;
+  InversePriorityQueue<std::pair<base::Time, std::string>> remove_queue_;
 
   using CallbackList = std::vector<CommandCallback>;
   CallbackList on_command_added_;
@@ -88,6 +96,9 @@
   std::map<std::string, Device::CommandHandlerCallback> command_callbacks_;
   Device::CommandHandlerCallback default_command_callback_;
 
+  // WeakPtr factory for controlling the lifetime of command queue cleanup
+  // tasks.
+  base::WeakPtrFactory<CommandQueue> weak_ptr_factory_{this};
   DISALLOW_COPY_AND_ASSIGN(CommandQueue);
 };
 
diff --git a/src/commands/command_queue_unittest.cc b/src/commands/command_queue_unittest.cc
index fdb9e81..1e2e0ac 100644
--- a/src/commands/command_queue_unittest.cc
+++ b/src/commands/command_queue_unittest.cc
@@ -10,12 +10,18 @@
 
 #include <base/bind.h>
 #include <base/memory/weak_ptr.h>
+#include <gmock/gmock.h>
 #include <gtest/gtest.h>
+#include <weave/provider/test/fake_task_runner.h>
 
+#include "src/bind_lambda.h"
 #include "src/string_utils.h"
 
 namespace weave {
 
+using testing::Return;
+using testing::StrictMock;
+
 class CommandQueueTest : public testing::Test {
  public:
   std::unique_ptr<CommandInstance> CreateDummyCommandInstance(
@@ -30,11 +36,15 @@
   bool Remove(const std::string& id) { return queue_.Remove(id); }
 
   void Cleanup(const base::TimeDelta& interval) {
-    queue_.SetNowForTest(base::Time::Now() + interval);
-    return queue_.Cleanup();
+    return queue_.Cleanup(task_runner_.GetClock()->Now() + interval);
   }
 
-  CommandQueue queue_;
+  std::string GetFirstCommandToBeRemoved() const {
+    return queue_.remove_queue_.top().second;
+  }
+
+  StrictMock<provider::test::FakeTaskRunner> task_runner_;
+  CommandQueue queue_{&task_runner_, task_runner_.GetClock()};
 };
 
 // Keeps track of commands being added to and removed from the queue_.
@@ -120,6 +130,46 @@
   EXPECT_EQ(0u, queue_.GetCount());
 }
 
+TEST_F(CommandQueueTest, RemoveLaterOnCleanupTask) {
+  const std::string id1 = "id1";
+  queue_.Add(CreateDummyCommandInstance("base.reboot", id1));
+  EXPECT_EQ(1u, queue_.GetCount());
+
+  queue_.RemoveLater(id1);
+  EXPECT_EQ(1u, queue_.GetCount());
+  ASSERT_EQ(1u, task_runner_.GetTaskQueueSize());
+
+  task_runner_.RunOnce();
+
+  EXPECT_EQ(0u, queue_.GetCount());
+  EXPECT_EQ(0u, task_runner_.GetTaskQueueSize());
+}
+
+TEST_F(CommandQueueTest, CleanupMultipleCommands) {
+  const std::string id1 = "id1";
+  const std::string id2 = "id2";
+
+  queue_.Add(CreateDummyCommandInstance("base.reboot", id1));
+  queue_.Add(CreateDummyCommandInstance("base.reboot", id2));
+  auto remove_task = [this](const std::string& id) { queue_.RemoveLater(id); };
+  remove_task(id1);
+  task_runner_.PostDelayedTask(FROM_HERE, base::Bind(remove_task, id2),
+                               base::TimeDelta::FromSeconds(10));
+  EXPECT_EQ(2u, queue_.GetCount());
+  ASSERT_EQ(2u, task_runner_.GetTaskQueueSize());
+  task_runner_.RunOnce();  // Executes "remove_task(id2) @ T+10s".
+  ASSERT_EQ(2u, queue_.GetCount());
+  ASSERT_EQ(1u, task_runner_.GetTaskQueueSize());
+  EXPECT_EQ(id1, GetFirstCommandToBeRemoved());
+  task_runner_.RunOnce();  // Should remove task "id1" from queue.
+  ASSERT_EQ(1u, queue_.GetCount());
+  ASSERT_EQ(1u, task_runner_.GetTaskQueueSize());
+  EXPECT_EQ(id2, GetFirstCommandToBeRemoved());
+  task_runner_.RunOnce();  // Should remove task "id2" from queue.
+  EXPECT_EQ(0u, queue_.GetCount());
+  EXPECT_EQ(0u, task_runner_.GetTaskQueueSize());
+}
+
 TEST_F(CommandQueueTest, Dispatch) {
   FakeDispatcher dispatch(&queue_);
   const std::string id1 = "id1";