diff --git a/services/tunnelbroker/src/Database/MessageItem.cpp b/services/tunnelbroker/src/Database/MessageItem.cpp
--- a/services/tunnelbroker/src/Database/MessageItem.cpp
+++ b/services/tunnelbroker/src/Database/MessageItem.cpp
@@ -69,11 +69,12 @@
 }
 
 PrimaryKeyDescriptor MessageItem::getPrimaryKeyDescriptor() const {
-  return PrimaryKeyDescriptor(MessageItem::FIELD_MESSAGE_ID);
+  return PrimaryKeyDescriptor(
+      MessageItem::FIELD_TO_DEVICE_ID, MessageItem::FIELD_MESSAGE_ID);
 }
 
 PrimaryKeyValue MessageItem::getPrimaryKeyValue() const {
-  return PrimaryKeyValue(this->messageID);
+  return PrimaryKeyValue(this->toDeviceID, this->messageID);
 }
 
 std::string MessageItem::getMessageID() const {