diff --git a/services/tunnelbroker/Cargo.lock b/services/tunnelbroker/Cargo.lock
--- a/services/tunnelbroker/Cargo.lock
+++ b/services/tunnelbroker/Cargo.lock
@@ -59,6 +59,21 @@
  "url",
 ]
 
+[[package]]
+name = "android-tzdata"
+version = "0.1.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e999941b234f3131b00bc13c22d06e8c5ff726d1b6318ac7eb276997bbb4fef0"
+
+[[package]]
+name = "android_system_properties"
+version = "0.1.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "819e7219dbd41043ac279b19830f2efc897156490d7fd6ea916720117ee66311"
+dependencies = [
+ "libc",
+]
+
 [[package]]
 name = "anstream"
 version = "0.3.2"
@@ -730,6 +745,20 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd"
 
+[[package]]
+name = "chrono"
+version = "0.4.31"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7f2c685bad3eb3d45a01354cedb7d5faa66194d1d58ba6e267a8de788f79db38"
+dependencies = [
+ "android-tzdata",
+ "iana-time-zone",
+ "js-sys",
+ "num-traits",
+ "wasm-bindgen",
+ "windows-targets 0.48.0",
+]
+
 [[package]]
 name = "cipher"
 version = "0.4.4"
@@ -1248,6 +1277,29 @@
  "tungstenite 0.20.0",
 ]
 
+[[package]]
+name = "iana-time-zone"
+version = "0.1.57"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "2fad5b825842d2b38bd206f3e81d6957625fd7f0a361e345c30e01a0ae2dd613"
+dependencies = [
+ "android_system_properties",
+ "core-foundation-sys",
+ "iana-time-zone-haiku",
+ "js-sys",
+ "wasm-bindgen",
+ "windows",
+]
+
+[[package]]
+name = "iana-time-zone-haiku"
+version = "0.1.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f31827a206f56af32e590ba56d5d2d085f558508192593743f16b2306495269f"
+dependencies = [
+ "cc",
+]
+
 [[package]]
 name = "idna"
 version = "0.3.0"
@@ -2589,6 +2641,7 @@
  "anyhow",
  "aws-config",
  "aws-sdk-dynamodb",
+ "chrono",
  "clap",
  "derive_more",
  "futures-util",
@@ -2825,6 +2878,15 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f"
 
+[[package]]
+name = "windows"
+version = "0.48.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e686886bc078bc1b0b600cac0147aadb815089b6e4da64016cbd754b6342700f"
+dependencies = [
+ "windows-targets 0.48.0",
+]
+
 [[package]]
 name = "windows-sys"
 version = "0.42.0"
diff --git a/services/tunnelbroker/Cargo.toml b/services/tunnelbroker/Cargo.toml
--- a/services/tunnelbroker/Cargo.toml
+++ b/services/tunnelbroker/Cargo.toml
@@ -27,6 +27,7 @@
 tunnelbroker_messages = { path = "../../shared/tunnelbroker_messages" }
 derive_more = "0.99.17"
 lapin = "2.2.1"
+chrono = "0.4.31"
 
 [build-dependencies]
 tonic-build = "0.8"
diff --git a/services/tunnelbroker/src/database/message_id.rs b/services/tunnelbroker/src/database/message_id.rs
new file mode 100644
--- /dev/null
+++ b/services/tunnelbroker/src/database/message_id.rs
@@ -0,0 +1,130 @@
+use chrono::{DateTime, Utc};
+
+#[derive(Debug, derive_more::Display, derive_more::Error)]
+enum ParseMessageIdError {
+  InvalidTimestamp(chrono::ParseError),
+  InvalidFormat,
+}
+#[derive(Debug)]
+struct MessageID {
+  timestamp: DateTime<Utc>,
+  client_message_id: String,
+}
+
+impl MessageID {
+  pub fn new(client_message_id: String) -> Self {
+    Self {
+      timestamp: Utc::now(),
+      client_message_id,
+    }
+  }
+}
+
+impl TryFrom<String> for MessageID {
+  type Error = ParseMessageIdError;
+
+  fn try_from(value: String) -> Result<Self, Self::Error> {
+    let parts: Vec<&str> = value.splitn(2, '#').collect();
+    if parts.len() != 2 {
+      return Err(ParseMessageIdError::InvalidFormat);
+    }
+
+    let timestamp = DateTime::parse_from_rfc3339(parts[0])
+      .map_err(ParseMessageIdError::InvalidTimestamp)?
+      .with_timezone(&Utc);
+
+    let client_message_id = parts[1].to_string();
+
+    Ok(Self {
+      timestamp,
+      client_message_id,
+    })
+  }
+}
+
+impl From<MessageID> for String {
+  fn from(value: MessageID) -> Self {
+    format!(
+      "{}#{}",
+      value.timestamp.to_rfc3339(),
+      value.client_message_id
+    )
+  }
+}
+
+#[cfg(test)]
+mod message_id_tests {
+  use super::*;
+  use std::convert::TryInto;
+
+  #[test]
+  fn test_into_string() {
+    let message_id = MessageID::new("abc123".to_string());
+
+    let message_id_string: String = message_id.into();
+    assert!(
+      message_id_string.contains("abc123"),
+      "Expected 'abc123' in the resulting string, but not found"
+    );
+
+    let parts: Vec<&str> = message_id_string.splitn(2, '#').collect();
+    assert_eq!(
+      parts.len(),
+      2,
+      "Expected the string to contain 2 parts separated by '#'"
+    );
+  }
+
+  #[test]
+  fn test_try_from_string_valid() {
+    let client_message_id = "abc123".to_string();
+    let timestamp = Utc::now().to_rfc3339();
+    let valid_string = format!("{}#{}", timestamp, client_message_id);
+
+    let message_id_result: Result<MessageID, _> = valid_string.try_into();
+
+    assert!(
+      message_id_result.is_ok(),
+      "Expected Ok, but found {:?}",
+      message_id_result
+    );
+    let message_id = message_id_result.unwrap();
+    assert_eq!(message_id.client_message_id, client_message_id);
+  }
+
+  #[test]
+  fn test_try_from_string_invalid_format() {
+    let message_id = MessageID::new("abc123".to_string());
+    let message_id_str: String = message_id.into();
+    let converted_message_id: Result<MessageID, _> = message_id_str.try_into();
+
+    assert!(
+      converted_message_id.is_ok(),
+      "Expected Ok, but found {:?}",
+      converted_message_id
+    );
+    let message_id_after_conversion = converted_message_id.unwrap();
+
+    assert_eq!(
+      message_id_after_conversion.client_message_id,
+      "abc123".to_string()
+    );
+  }
+
+  #[test]
+  fn test_conversion() {
+    let client_message_id = "abc123".to_string();
+    let timestamp = Utc::now().to_rfc3339();
+    let valid_string = format!("{}#{}", timestamp, client_message_id);
+
+    let message_id_result: Result<MessageID, _> = valid_string.try_into();
+
+    assert!(
+      message_id_result.is_ok(),
+      "Expected Ok, but found {:?}",
+      message_id_result
+    );
+    let message_id = message_id_result.unwrap();
+    assert_eq!(message_id.client_message_id, client_message_id);
+  }
+}
diff --git a/services/tunnelbroker/src/database/mod.rs b/services/tunnelbroker/src/database/mod.rs
--- a/services/tunnelbroker/src/database/mod.rs
+++ b/services/tunnelbroker/src/database/mod.rs
@@ -16,6 +16,8 @@
 };
 
 pub mod message;
+pub mod message_id;
+
 pub use message::*;
 
 #[derive(Clone)]