diff --git a/buffet/commands/command_instance.cc b/buffet/commands/command_instance.cc
new file mode 100644
index 0000000..7c5e122
--- /dev/null
+++ b/buffet/commands/command_instance.cc
@@ -0,0 +1,25 @@
+// Copyright 2014 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "buffet/commands/command_instance.h"
+
+namespace buffet {
+
+CommandInstance::CommandInstance(const std::string& name,
+                                 const std::string& category,
+                                 const native_types::Object& parameters)
+    : name_(name), category_(category), parameters_(parameters) {
+}
+
+std::shared_ptr<const PropValue> CommandInstance::FindParameter(
+    const std::string& name) const {
+  std::shared_ptr<const PropValue> value;
+  auto p = parameters_.find(name);
+  if (p != parameters_.end())
+    value = p->second;
+  return value;
+}
+
+
+}  // namespace buffet
diff --git a/buffet/commands/command_instance.h b/buffet/commands/command_instance.h
new file mode 100644
index 0000000..0028c88
--- /dev/null
+++ b/buffet/commands/command_instance.h
@@ -0,0 +1,52 @@
+// Copyright 2014 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef BUFFET_COMMANDS_COMMAND_INSTANCE_H_
+#define BUFFET_COMMANDS_COMMAND_INSTANCE_H_
+
+#include <map>
+#include <memory>
+#include <string>
+
+#include <base/basictypes.h>
+
+#include "buffet/commands/prop_values.h"
+#include "buffet/commands/schema_utils.h"
+
+namespace buffet {
+
+class CommandInstance final {
+ public:
+  // Construct a command instance given the full command |name| which must
+  // be in format "<package_name>.<command_name>", a command |category| and
+  // a list of parameters and their values specified in |parameters|.
+  CommandInstance(const std::string& name, const std::string& category,
+                  const native_types::Object& parameters);
+
+  // Returns the full name of the command.
+  const std::string& GetName() const { return name_; }
+  // Returns the command category.
+  const std::string& GetCategory() const { return category_; }
+  // Returns the command parameters and their values.
+  const native_types::Object& GetParameters() const { return parameters_; }
+  // Finds a command parameter value by parameter |name|. If the parameter
+  // with given name does not exist, returns null shared_ptr.
+  std::shared_ptr<const PropValue> FindParameter(const std::string& name) const;
+
+ private:
+  // Full command name as "<package_name>.<command_name>".
+  std::string name_;
+  // Command category. See comments for CommandDefinitions::LoadCommands for the
+  // detailed description of what command categories are and what they are used
+  // for.
+  std::string category_;
+  // Command parameters and their values.
+  native_types::Object parameters_;
+
+  DISALLOW_COPY_AND_ASSIGN(CommandInstance);
+};
+
+}  // namespace buffet
+
+#endif  // BUFFET_COMMANDS_COMMAND_INSTANCE_H_
diff --git a/buffet/commands/command_instance_unittest.cc b/buffet/commands/command_instance_unittest.cc
new file mode 100644
index 0000000..0577004
--- /dev/null
+++ b/buffet/commands/command_instance_unittest.cc
@@ -0,0 +1,25 @@
+// Copyright 2014 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <gtest/gtest.h>
+
+#include "buffet/commands/command_instance.h"
+#include "buffet/commands/prop_types.h"
+
+TEST(CommandInstance, Test) {
+  buffet::native_types::Object params;
+  buffet::IntPropType int_prop;
+  buffet::DoublePropType dbl_prop;
+  params.insert(std::make_pair("freq", dbl_prop.CreateValue(800.5)));
+  params.insert(std::make_pair("volume", int_prop.CreateValue(100)));
+  buffet::CommandInstance instance("robot._beep", "robotd", params);
+
+  EXPECT_EQ("robot._beep", instance.GetName());
+  EXPECT_EQ("robotd", instance.GetCategory());
+  EXPECT_EQ(params, instance.GetParameters());
+  EXPECT_DOUBLE_EQ(800.5,
+                   instance.FindParameter("freq")->GetDouble()->GetValue());
+  EXPECT_EQ(100, instance.FindParameter("volume")->GetInt()->GetValue());
+  EXPECT_EQ(nullptr, instance.FindParameter("blah").get());
+}
diff --git a/buffet/commands/command_queue.cc b/buffet/commands/command_queue.cc
new file mode 100644
index 0000000..ca1e7f9
--- /dev/null
+++ b/buffet/commands/command_queue.cc
@@ -0,0 +1,33 @@
+// Copyright 2014 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "buffet/commands/command_queue.h"
+
+namespace buffet {
+
+std::string CommandQueue::Add(std::unique_ptr<const CommandInstance> instance) {
+  std::string id = std::to_string(++next_id_);
+  auto pair = map_.insert(std::make_pair(id, std::move(instance)));
+  LOG_IF(FATAL, !pair.second) << "Command with ID '" << id
+                              << "' is already in the queue";
+  return id;
+}
+
+std::unique_ptr<const CommandInstance> CommandQueue::Remove(
+    const std::string& id) {
+  std::unique_ptr<const CommandInstance> instance;
+  auto p = map_.find(id);
+  if (p != map_.end()) {
+    instance = std::move(p->second);
+    map_.erase(p);
+  }
+  return instance;
+}
+
+const CommandInstance* CommandQueue::Find(const std::string& id) const {
+  auto p = map_.find(id);
+  return (p != map_.end()) ? p->second.get() : nullptr;
+}
+
+}  // namespace buffet
diff --git a/buffet/commands/command_queue.h b/buffet/commands/command_queue.h
new file mode 100644
index 0000000..5d650a0
--- /dev/null
+++ b/buffet/commands/command_queue.h
@@ -0,0 +1,54 @@
+// Copyright 2014 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef BUFFET_COMMANDS_COMMAND_QUEUE_H_
+#define BUFFET_COMMANDS_COMMAND_QUEUE_H_
+
+#include <map>
+#include <memory>
+#include <string>
+
+#include <base/basictypes.h>
+
+#include "buffet/commands/command_instance.h"
+
+namespace buffet {
+
+class CommandQueue final {
+ public:
+  CommandQueue() = default;
+
+  // Checks if the command queue is empty.
+  bool IsEmpty() const { return map_.empty(); }
+
+  // Returns the number of commands in the queue.
+  size_t GetCount() const { return map_.size(); }
+
+  // Adds a new command to the queue. Each command in the queue has a unique
+  // ID that identifies that command instance. The ID string of the added
+  // command is returned by this method.
+  std::string Add(std::unique_ptr<const 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<const CommandInstance> Remove(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
+  // pointer should not be persisted for a long period of time.
+  const CommandInstance* Find(const std::string& id) const;
+
+ private:
+  // ID-to-CommandInstance map.
+  std::map<std::string, std::unique_ptr<const CommandInstance>> map_;
+  // Counter for generating unique command IDs.
+  int next_id_ = 0;
+
+  DISALLOW_COPY_AND_ASSIGN(CommandQueue);
+};
+
+}  // namespace buffet
+
+#endif  // BUFFET_COMMANDS_COMMAND_QUEUE_H_
diff --git a/buffet/commands/command_queue_unittest.cc b/buffet/commands/command_queue_unittest.cc
new file mode 100644
index 0000000..d116e96
--- /dev/null
+++ b/buffet/commands/command_queue_unittest.cc
@@ -0,0 +1,65 @@
+// Copyright 2014 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <string>
+
+#include <gtest/gtest.h>
+
+#include "buffet/commands/command_queue.h"
+
+namespace {
+
+std::unique_ptr<const buffet::CommandInstance> CreateDummyCommandInstance(
+    const std::string& name = "base.reboot") {
+  return std::unique_ptr<const buffet::CommandInstance>(
+      new buffet::CommandInstance(name, "powerd", {}));
+}
+
+}  // anonymous namespace
+
+TEST(CommandQueue, Empty) {
+  buffet::CommandQueue queue;
+  EXPECT_TRUE(queue.IsEmpty());
+  EXPECT_EQ(0, queue.GetCount());
+}
+
+TEST(CommandQueue, Add) {
+  buffet::CommandQueue queue;
+  EXPECT_EQ("1", queue.Add(CreateDummyCommandInstance()));
+  EXPECT_EQ("2", queue.Add(CreateDummyCommandInstance()));
+  EXPECT_EQ("3", queue.Add(CreateDummyCommandInstance()));
+  EXPECT_EQ(3, queue.GetCount());
+  EXPECT_FALSE(queue.IsEmpty());
+}
+
+TEST(CommandQueue, Remove) {
+  buffet::CommandQueue queue;
+  std::string id1 = queue.Add(CreateDummyCommandInstance());
+  std::string id2 = queue.Add(CreateDummyCommandInstance());
+  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());
+}
+
+TEST(CommandQueue, Find) {
+  buffet::CommandQueue queue;
+  std::string id1 = queue.Add(CreateDummyCommandInstance("base.reboot"));
+  std::string id2 = queue.Add(CreateDummyCommandInstance("base.shutdown"));
+  EXPECT_EQ(nullptr, queue.Find("dummy"));
+  auto cmd1 = queue.Find(id1);
+  EXPECT_NE(nullptr, cmd1);
+  EXPECT_EQ("base.reboot", cmd1->GetName());
+  auto cmd2 = queue.Find(id2);
+  EXPECT_NE(nullptr, cmd2);
+  EXPECT_EQ("base.shutdown", cmd2->GetName());
+}
diff --git a/buffet/commands/schema_utils.h b/buffet/commands/schema_utils.h
index ff9d461..0f89e27 100644
--- a/buffet/commands/schema_utils.h
+++ b/buffet/commands/schema_utils.h
@@ -23,7 +23,7 @@
 
 namespace native_types {
 // C++ representation of object values.
-using Object = std::map<std::string, std::shared_ptr<PropValue>>;
+using Object = std::map<std::string, std::shared_ptr<const PropValue>>;
 }  // namespace native_types
 // Converts an object to string.
 std::string ToString(const native_types::Object& obj);