diff --git a/virtualizationservice/Android.bp b/virtualizationservice/Android.bp
index 843873b..2cbc805 100644
--- a/virtualizationservice/Android.bp
+++ b/virtualizationservice/Android.bp
@@ -31,12 +31,14 @@
         "libanyhow",
         "libavflog",
         "libbinder_rs",
+        "libhex",
         "libhypervisor_props",
         "liblazy_static",
         "liblibc",
         "liblog_rust",
         "libnix",
         "libopenssl",
+        "librand",
         "librkpd_client",
         "librustutils",
         "libstatslog_virtualization_rust",
diff --git a/virtualizationservice/aidl/android/system/virtualizationservice/IVirtualizationService.aidl b/virtualizationservice/aidl/android/system/virtualizationservice/IVirtualizationService.aidl
index f7bbf55..e11d8b8 100644
--- a/virtualizationservice/aidl/android/system/virtualizationservice/IVirtualizationService.aidl
+++ b/virtualizationservice/aidl/android/system/virtualizationservice/IVirtualizationService.aidl
@@ -41,6 +41,11 @@
             in @nullable ParcelFileDescriptor osLogFd);
 
     /**
+     * Allocate an instance_id to the (newly created) VM.
+     */
+    byte[64] allocateInstanceId();
+
+    /**
      * Initialise an empty partition image of the given size to be used as a writable partition.
      *
      * The file must be open with both read and write permissions, and should be a new empty file.
diff --git a/virtualizationservice/aidl/android/system/virtualizationservice/VirtualMachineAppConfig.aidl b/virtualizationservice/aidl/android/system/virtualizationservice/VirtualMachineAppConfig.aidl
index 8302a2f..29232ff 100644
--- a/virtualizationservice/aidl/android/system/virtualizationservice/VirtualMachineAppConfig.aidl
+++ b/virtualizationservice/aidl/android/system/virtualizationservice/VirtualMachineAppConfig.aidl
@@ -23,6 +23,9 @@
     /** Name of VM */
     String name;
 
+    /** Id of the VM instance */
+    byte[64] instanceId;
+
     /** Main APK */
     ParcelFileDescriptor apk;
 
diff --git a/virtualizationservice/aidl/android/system/virtualizationservice/VirtualMachineRawConfig.aidl b/virtualizationservice/aidl/android/system/virtualizationservice/VirtualMachineRawConfig.aidl
index 6be2833..b2116c4 100644
--- a/virtualizationservice/aidl/android/system/virtualizationservice/VirtualMachineRawConfig.aidl
+++ b/virtualizationservice/aidl/android/system/virtualizationservice/VirtualMachineRawConfig.aidl
@@ -23,6 +23,9 @@
     /** Name of VM */
     String name;
 
+    /** Id of the VM instance */
+    byte[64] instanceId;
+
     /** The kernel image, if any. */
     @nullable ParcelFileDescriptor kernel;
 
diff --git a/virtualizationservice/aidl/android/system/virtualizationservice_internal/IVirtualizationServiceInternal.aidl b/virtualizationservice/aidl/android/system/virtualizationservice_internal/IVirtualizationServiceInternal.aidl
index abfc45a..fc36190 100644
--- a/virtualizationservice/aidl/android/system/virtualizationservice_internal/IVirtualizationServiceInternal.aidl
+++ b/virtualizationservice/aidl/android/system/virtualizationservice_internal/IVirtualizationServiceInternal.aidl
@@ -91,4 +91,9 @@
 
     /** Returns a read-only file descriptor of the VM DTBO file. */
     ParcelFileDescriptor getDtboFile();
+
+    /**
+     * Allocate an instance_id to the (newly created) VM.
+     */
+    byte[64] allocateInstanceId();
 }
diff --git a/virtualizationservice/src/aidl.rs b/virtualizationservice/src/aidl.rs
index c7ae5f0..79ff89a 100644
--- a/virtualizationservice/src/aidl.rs
+++ b/virtualizationservice/src/aidl.rs
@@ -35,6 +35,7 @@
 use log::{error, info, warn};
 use nix::unistd::{chown, Uid};
 use openssl::x509::X509;
+use rand::Fill;
 use rkpd_client::get_rkpd_attestation_key;
 use rustutils::system_properties;
 use serde::Deserialize;
@@ -378,6 +379,17 @@
         let file = state.get_dtbo_file().or_service_specific_exception(-1)?;
         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())
+            .context("Failed to allocate instance_id")
+            .or_service_specific_exception(-1)?;
+        let uid = get_calling_uid();
+        info!("Allocated a VM's instance_id: {:?}, for uid: {:?}", hex::encode(id), uid);
+        Ok(id)
+    }
 }
 
 // KEEP IN SYNC WITH assignable_devices.xsd