diff --git a/services/tunnelbroker/Cargo.lock b/services/tunnelbroker/Cargo.lock
--- a/services/tunnelbroker/Cargo.lock
+++ b/services/tunnelbroker/Cargo.lock
@@ -2659,6 +2659,7 @@
  "tracing",
  "tracing-subscriber",
  "tunnelbroker_messages",
+ "uuid",
 ]
 
 [[package]]
@@ -2731,6 +2732,15 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "711b9620af191e0cdc7468a8d14e709c3dcdb115b36f838e601583af800a370a"
 
+[[package]]
+name = "uuid"
+version = "1.4.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "79daa5ed5740825c40b389c5e50312b9c86df53fccd33f281df655642b43869d"
+dependencies = [
+ "getrandom",
+]
+
 [[package]]
 name = "valuable"
 version = "0.1.0"
diff --git a/services/tunnelbroker/Cargo.toml b/services/tunnelbroker/Cargo.toml
--- a/services/tunnelbroker/Cargo.toml
+++ b/services/tunnelbroker/Cargo.toml
@@ -28,6 +28,7 @@
 derive_more = "0.99.17"
 lapin = "2.2.1"
 chrono = "0.4.31"
+uuid = { version = "1.2", features = ["v4"] }
 
 [build-dependencies]
 tonic-build = "0.8"
diff --git a/services/tunnelbroker/src/grpc/mod.rs b/services/tunnelbroker/src/grpc/mod.rs
--- a/services/tunnelbroker/src/grpc/mod.rs
+++ b/services/tunnelbroker/src/grpc/mod.rs
@@ -37,9 +37,11 @@
 
     debug!("Received message for {}", &message.device_id);
 
+    let client_message_id = uuid::Uuid::new_v4().to_string();
+
     self
       .client
-      .persist_message(&message.device_id, &message.payload, "message_id")
+      .persist_message(&message.device_id, &message.payload, &client_message_id)
       .await
       .map_err(handle_ddb_error)?;