diff --git a/virtualizationservice/src/aidl.rs b/virtualizationservice/src/aidl.rs
index bbfb220..2fe14c0 100644
--- a/virtualizationservice/src/aidl.rs
+++ b/virtualizationservice/src/aidl.rs
@@ -39,7 +39,10 @@
 use openssl::x509::X509;
 use rand::Fill;
 use rkpd_client::get_rkpd_attestation_key;
-use rustutils::system_properties;
+use rustutils::{
+    system_properties,
+    users::{multiuser_get_app_id, multiuser_get_user_id},
+};
 use serde::Deserialize;
 use service_vm_comm::Response;
 use std::collections::{HashMap, HashSet};
@@ -385,7 +388,6 @@
         Ok(ParcelFileDescriptor::new(file))
     }
 
-    // TODO(b/294177871) Persist this Id, along with client uuid.
     fn allocateInstanceId(&self) -> binder::Result<[u8; 64]> {
         let mut id = [0u8; 64];
         id.try_fill(&mut rand::thread_rng())
@@ -393,6 +395,16 @@
             .or_service_specific_exception(-1)?;
         let uid = get_calling_uid();
         info!("Allocated a VM's instance_id: {:?}, for uid: {:?}", hex::encode(id), uid);
+        let state = &mut *self.state.lock().unwrap();
+        if let Some(sk_state) = &mut state.sk_state {
+            let user_id = multiuser_get_user_id(uid);
+            let app_id = multiuser_get_app_id(uid);
+            info!("Recording potential existence of state for (user_id={user_id}, app_id={app_id}");
+            if let Err(e) = sk_state.add_id(&id, user_id, app_id) {
+                error!("Failed to record the instance_id: {e:?}");
+            }
+        }
+
         Ok(id)
     }
 
diff --git a/virtualizationservice/src/maintenance.rs b/virtualizationservice/src/maintenance.rs
index 7fc2f37..0a367c5 100644
--- a/virtualizationservice/src/maintenance.rs
+++ b/virtualizationservice/src/maintenance.rs
@@ -15,7 +15,7 @@
 use android_hardware_security_secretkeeper::aidl::android::hardware::security::secretkeeper::{
     ISecretkeeper::ISecretkeeper, SecretId::SecretId,
 };
-use anyhow::Result;
+use anyhow::{Context, Result};
 use log::{error, info, warn};
 
 mod vmdb;
@@ -88,6 +88,13 @@
         }
     }
 
+    /// Record a new VM ID.
+    pub fn add_id(&mut self, vm_id: &VmId, user_id: u32, app_id: u32) -> Result<()> {
+        let user_id: i32 = user_id.try_into().context(format!("user_id {user_id} out of range"))?;
+        let app_id: i32 = app_id.try_into().context(format!("app_id {app_id} out of range"))?;
+        self.vm_id_db.add_vm_id(vm_id, user_id, app_id)
+    }
+
     /// Delete the VM IDs associated with Android user ID `user_id`.
     pub fn delete_ids_for_user(&mut self, user_id: i32) -> Result<()> {
         let vm_ids = self.vm_id_db.vm_ids_for_user(user_id)?;
diff --git a/virtualizationservice/src/maintenance/vmdb.rs b/virtualizationservice/src/maintenance/vmdb.rs
index bdff034..63a28a4 100644
--- a/virtualizationservice/src/maintenance/vmdb.rs
+++ b/virtualizationservice/src/maintenance/vmdb.rs
@@ -119,7 +119,6 @@
     }
 
     /// Add the given VM ID into the database.
-    #[allow(dead_code)] // TODO(b/294177871): connect this up
     pub fn add_vm_id(&mut self, vm_id: &VmId, user_id: i32, app_id: i32) -> Result<()> {
         let _rows = self
             .conn