diff --git a/buffet/commands/command_instance.cc b/buffet/commands/command_instance.cc
index 926dcf5..c12f1ed 100644
--- a/buffet/commands/command_instance.cc
+++ b/buffet/commands/command_instance.cc
@@ -215,12 +215,8 @@
 }
 
 void CommandInstance::RemoveFromQueue() {
-  if (queue_) {
-    // Store this instance in unique_ptr until the end of this method,
-    // otherwise it will be destroyed as soon as CommandQueue::Remove() returns.
-    std::unique_ptr<CommandInstance> this_instance = queue_->Remove(GetID());
-    // The command instance will survive till the end of this scope.
-  }
+  if (queue_)
+    queue_->DelayedRemove(GetID());
 }
 
 
diff --git a/buffet/commands/command_queue.cc b/buffet/commands/command_queue.cc
index d660a1d..62d8c20 100644
--- a/buffet/commands/command_queue.cc
+++ b/buffet/commands/command_queue.cc
@@ -4,10 +4,16 @@
 
 #include "buffet/commands/command_queue.h"
 
+#include <base/time/time.h>
+
 #include "buffet/commands/command_dispatch_interface.h"
 
 namespace buffet {
 
+namespace {
+const int kRemoveCommandDelayMin = 5;
+}
+
 void CommandQueue::Add(std::unique_ptr<CommandInstance> instance) {
   std::string id = instance->GetID();
   LOG_IF(FATAL, id.empty()) << "Command has no ID";
@@ -17,20 +23,44 @@
                               << "' is already in the queue";
   if (dispatch_interface_)
     dispatch_interface_->OnCommandAdded(pair.first->second.get());
+  Cleanup();
 }
 
-std::unique_ptr<CommandInstance> CommandQueue::Remove(
-    const std::string& id) {
-  std::unique_ptr<CommandInstance> instance;
+void CommandQueue::DelayedRemove(const std::string& id) {
   auto p = map_.find(id);
-  if (p != map_.end()) {
-    instance = std::move(p->second);
-    instance->SetCommandQueue(nullptr);
-    map_.erase(p);
-    if (dispatch_interface_)
-      dispatch_interface_->OnCommandRemoved(instance.get());
+  if (p == map_.end())
+    return;
+  remove_queue_.push(std::make_pair(
+      base::Time::Now() + base::TimeDelta::FromMinutes(kRemoveCommandDelayMin),
+      id));
+  Cleanup();
+}
+
+bool CommandQueue::Remove(const std::string& id) {
+  auto p = map_.find(id);
+  if (p == map_.end())
+    return false;
+  std::unique_ptr<CommandInstance> instance{std::move(p->second)};
+  instance->SetCommandQueue(nullptr);
+  map_.erase(p);
+  if (dispatch_interface_)
+    dispatch_interface_->OnCommandRemoved(instance.get());
+  return true;
+}
+
+void CommandQueue::Cleanup() {
+  while (!remove_queue_.empty() && remove_queue_.front().first < Now()) {
+    Remove(remove_queue_.front().second);
+    remove_queue_.pop();
   }
-  return instance;
+}
+
+void CommandQueue::SetNowForTest(base::Time now) {
+  test_now_ = now;
+}
+
+base::Time CommandQueue::Now() const {
+  return test_now_.is_null() ? base::Time::Now() : test_now_;
 }
 
 CommandInstance* CommandQueue::Find(const std::string& id) const {
diff --git a/buffet/commands/command_queue.h b/buffet/commands/command_queue.h
index 6d6547d..09339d9 100644
--- a/buffet/commands/command_queue.h
+++ b/buffet/commands/command_queue.h
@@ -7,7 +7,9 @@
 
 #include <map>
 #include <memory>
+#include <queue>
 #include <string>
+#include <utility>
 
 #include <base/macros.h>
 
@@ -39,10 +41,9 @@
   // One shouldn't attempt to add a command with the same ID.
   void Add(std::unique_ptr<CommandInstance> instance);
 
-  // Removes a command identified by |id| from the queue. Returns a unique
-  // pointer to the command instance if removed successfully, or an empty
-  // unique_ptr if the command with the given ID doesn't exist in the queue.
-  std::unique_ptr<CommandInstance> Remove(const std::string& id);
+  // Selects command identified by |id| ready for removal. Command will actually
+  // be removed after some time.
+  void DelayedRemove(const std::string& id);
 
   // Finds a command instance in the queue by the instance |id|. Returns
   // nullptr if the command with the given |id| is not found. The returned
@@ -50,8 +51,30 @@
   CommandInstance* Find(const std::string& id) const;
 
  private:
+  friend class CommandQueueTest;
+  friend class DBusCommandDispacherTest;
+
+  // Removes a command identified by |id| from the queue.
+  bool Remove(const std::string& id);
+
+  // Removes old commands selected with DelayedRemove.
+  void Cleanup();
+
+  // Overrides CommandQueue::Now() for tests.
+  void SetNowForTest(base::Time now);
+
+  // Returns current time.
+  base::Time Now() const;
+
+  // Overrided value to be returned from Now().
+  base::Time test_now_;
+
   // ID-to-CommandInstance map.
   std::map<std::string, std::unique_ptr<CommandInstance>> map_;
+
+  // Queue of commands to be removed.
+  std::queue<std::pair<base::Time, std::string>> remove_queue_;
+
   // Callback interface for command dispatch, if provided.
   CommandDispachInterface* dispatch_interface_ = nullptr;
 
diff --git a/buffet/commands/command_queue_unittest.cc b/buffet/commands/command_queue_unittest.cc
index 9587797..3e4b6ab 100644
--- a/buffet/commands/command_queue_unittest.cc
+++ b/buffet/commands/command_queue_unittest.cc
@@ -15,36 +15,47 @@
 #include "buffet/commands/command_dispatch_interface.h"
 #include "buffet/commands/object_schema.h"
 
-namespace {
+namespace buffet {
 
 class CommandQueueTest : public testing::Test {
  public:
-  std::unique_ptr<buffet::CommandInstance> CreateDummyCommandInstance(
-      const std::string& name, const std::string& id) {
-    std::unique_ptr<buffet::CommandInstance> cmd{
-      new buffet::CommandInstance{name, &command_definition_, {}}};
+  std::unique_ptr<CommandInstance> CreateDummyCommandInstance(
+      const std::string& name,
+      const std::string& id) {
+    std::unique_ptr<CommandInstance> cmd{
+        new CommandInstance{name, &command_definition_, {}}};
     cmd->SetID(id);
     return cmd;
   }
 
+  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();
+  }
+
+  CommandQueue queue_;
+
  private:
-  buffet::CommandDefinition command_definition_{
-      "powerd", buffet::ObjectSchema::Create(), buffet::ObjectSchema::Create()};
+  CommandDefinition command_definition_{"powerd",
+                                        ObjectSchema::Create(),
+                                        ObjectSchema::Create()};
 };
 
 // Fake implementation of CommandDispachInterface.
-// Just keeps track of commands being added to and removed from the queue.
+// Just keeps track of commands being added to and removed from the queue_.
 // Aborts if duplicate commands are added or non-existent commands are removed.
-class FakeDispatchInterface : public buffet::CommandDispachInterface {
+class FakeDispatchInterface : public CommandDispachInterface {
  public:
-  void OnCommandAdded(buffet::CommandInstance* command_instance) override {
+  void OnCommandAdded(CommandInstance* command_instance) override {
     CHECK(ids_.insert(command_instance->GetID()).second)
         << "Command ID already exists: " << command_instance->GetID();
     CHECK(commands_.insert(command_instance).second)
         << "Command instance already exists";
   }
 
-  void OnCommandRemoved(buffet::CommandInstance* command_instance) override {
+  void OnCommandRemoved(CommandInstance* command_instance) override {
     CHECK_EQ(1, ids_.erase(command_instance->GetID()))
         << "Command ID not found: " << command_instance->GetID();
     CHECK_EQ(1, commands_.erase(command_instance))
@@ -52,7 +63,7 @@
   }
 
   // Get the comma-separated list of command IDs currently accumulated in the
-  // command queue.
+  // command queue_.
   std::string GetIDs() const {
     using chromeos::string_utils::Join;
     return Join(",", std::vector<std::string>(ids_.begin(), ids_.end()));
@@ -60,77 +71,88 @@
 
  private:
   std::set<std::string> ids_;
-  std::set<buffet::CommandInstance*> commands_;
+  std::set<CommandInstance*> commands_;
 };
 
-}  // anonymous namespace
-
 TEST_F(CommandQueueTest, Empty) {
-  buffet::CommandQueue queue;
-  EXPECT_TRUE(queue.IsEmpty());
-  EXPECT_EQ(0, queue.GetCount());
+  EXPECT_TRUE(queue_.IsEmpty());
+  EXPECT_EQ(0, queue_.GetCount());
 }
 
 TEST_F(CommandQueueTest, Add) {
-  buffet::CommandQueue queue;
-  queue.Add(CreateDummyCommandInstance("base.reboot", "id1"));
-  queue.Add(CreateDummyCommandInstance("base.reboot", "id2"));
-  queue.Add(CreateDummyCommandInstance("base.reboot", "id3"));
-  EXPECT_EQ(3, queue.GetCount());
-  EXPECT_FALSE(queue.IsEmpty());
+  queue_.Add(CreateDummyCommandInstance("base.reboot", "id1"));
+  queue_.Add(CreateDummyCommandInstance("base.reboot", "id2"));
+  queue_.Add(CreateDummyCommandInstance("base.reboot", "id3"));
+  EXPECT_EQ(3, queue_.GetCount());
+  EXPECT_FALSE(queue_.IsEmpty());
 }
 
 TEST_F(CommandQueueTest, Remove) {
-  buffet::CommandQueue queue;
   const std::string id1 = "id1";
   const std::string id2 = "id2";
-  queue.Add(CreateDummyCommandInstance("base.reboot", id1));
-  queue.Add(CreateDummyCommandInstance("base.reboot", id2));
-  EXPECT_FALSE(queue.IsEmpty());
-  EXPECT_EQ(nullptr, queue.Remove("dummy").get());
-  EXPECT_EQ(2, queue.GetCount());
-  EXPECT_NE(nullptr, queue.Remove(id1).get());
-  EXPECT_EQ(1, queue.GetCount());
-  EXPECT_EQ(nullptr, queue.Remove(id1).get());
-  EXPECT_EQ(1, queue.GetCount());
-  EXPECT_NE(nullptr, queue.Remove(id2).get());
-  EXPECT_EQ(0, queue.GetCount());
-  EXPECT_EQ(nullptr, queue.Remove(id2).get());
-  EXPECT_EQ(0, queue.GetCount());
-  EXPECT_TRUE(queue.IsEmpty());
+  queue_.Add(CreateDummyCommandInstance("base.reboot", id1));
+  queue_.Add(CreateDummyCommandInstance("base.reboot", id2));
+  EXPECT_FALSE(queue_.IsEmpty());
+  EXPECT_FALSE(Remove("dummy"));
+  EXPECT_EQ(2, queue_.GetCount());
+  EXPECT_TRUE(Remove(id1));
+  EXPECT_EQ(1, queue_.GetCount());
+  EXPECT_FALSE(Remove(id1));
+  EXPECT_EQ(1, queue_.GetCount());
+  EXPECT_TRUE(Remove(id2));
+  EXPECT_EQ(0, queue_.GetCount());
+  EXPECT_FALSE(Remove(id2));
+  EXPECT_EQ(0, queue_.GetCount());
+  EXPECT_TRUE(queue_.IsEmpty());
+}
+
+TEST_F(CommandQueueTest, DelayedRemove) {
+  const std::string id1 = "id1";
+  queue_.Add(CreateDummyCommandInstance("base.reboot", id1));
+  EXPECT_EQ(1, queue_.GetCount());
+
+  queue_.DelayedRemove(id1);
+  EXPECT_EQ(1, queue_.GetCount());
+
+  Cleanup(base::TimeDelta::FromMinutes(1));
+  EXPECT_EQ(1, queue_.GetCount());
+
+  Cleanup(base::TimeDelta::FromMinutes(15));
+  EXPECT_EQ(0, queue_.GetCount());
 }
 
 TEST_F(CommandQueueTest, Dispatch) {
   FakeDispatchInterface dispatch;
-  buffet::CommandQueue queue;
-  queue.SetCommandDispachInterface(&dispatch);
+  queue_.SetCommandDispachInterface(&dispatch);
   const std::string id1 = "id1";
   const std::string id2 = "id2";
-  queue.Add(CreateDummyCommandInstance("base.reboot", id1));
-  queue.Add(CreateDummyCommandInstance("base.reboot", id2));
+  queue_.Add(CreateDummyCommandInstance("base.reboot", id1));
+  queue_.Add(CreateDummyCommandInstance("base.reboot", id2));
   std::set<std::string> ids{id1, id2};  // Make sure they are sorted properly.
   std::string expected_set = chromeos::string_utils::Join(
       ",", std::vector<std::string>(ids.begin(), ids.end()));
   EXPECT_EQ(expected_set, dispatch.GetIDs());
-  queue.Remove(id1);
+  Remove(id1);
   EXPECT_EQ(id2, dispatch.GetIDs());
-  queue.Remove(id2);
+  Remove(id2);
   EXPECT_EQ("", dispatch.GetIDs());
+  queue_.SetCommandDispachInterface(nullptr);
 }
 
 TEST_F(CommandQueueTest, Find) {
-  buffet::CommandQueue queue;
   const std::string id1 = "id1";
   const std::string id2 = "id2";
-  queue.Add(CreateDummyCommandInstance("base.reboot", id1));
-  queue.Add(CreateDummyCommandInstance("base.shutdown", id2));
-  EXPECT_EQ(nullptr, queue.Find("dummy"));
-  auto cmd1 = queue.Find(id1);
+  queue_.Add(CreateDummyCommandInstance("base.reboot", id1));
+  queue_.Add(CreateDummyCommandInstance("base.shutdown", id2));
+  EXPECT_EQ(nullptr, queue_.Find("dummy"));
+  auto cmd1 = queue_.Find(id1);
   EXPECT_NE(nullptr, cmd1);
   EXPECT_EQ("base.reboot", cmd1->GetName());
   EXPECT_EQ(id1, cmd1->GetID());
-  auto cmd2 = queue.Find(id2);
+  auto cmd2 = queue_.Find(id2);
   EXPECT_NE(nullptr, cmd2);
   EXPECT_EQ("base.shutdown", cmd2->GetName());
   EXPECT_EQ(id2, cmd2->GetID());
 }
+
+}  // namespace buffet
diff --git a/buffet/commands/dbus_command_dispatcher_unittest.cc b/buffet/commands/dbus_command_dispatcher_unittest.cc
index ec3c658..1e27aac 100644
--- a/buffet/commands/dbus_command_dispatcher_unittest.cc
+++ b/buffet/commands/dbus_command_dispatcher_unittest.cc
@@ -30,7 +30,6 @@
 namespace buffet {
 
 namespace {
-
 const char kCommandCategory[] = "test_category";
 
 }  // anonymous namespace
@@ -38,6 +37,8 @@
 class DBusCommandDispacherTest : public testing::Test {
  public:
   void SetUp() override {
+    command_queue_.SetNowForTest(base::Time::Max());
+
     const dbus::ObjectPath kExportedObjectManagerPath("/test/om_path");
     std::string cmd_path = dbus_constants::kCommandServicePathPrefix;
     cmd_path += "1";