diff --git a/java/framework/src/android/system/virtualmachine/VirtualMachine.java b/java/framework/src/android/system/virtualmachine/VirtualMachine.java
index c5778fb..d746c7c 100644
--- a/java/framework/src/android/system/virtualmachine/VirtualMachine.java
+++ b/java/framework/src/android/system/virtualmachine/VirtualMachine.java
@@ -457,8 +457,8 @@
         } catch (VirtualMachineException | RuntimeException e) {
             // If anything goes wrong, delete any files created so far and the VM's directory
             try {
-                deleteRecursively(vmDir);
-            } catch (IOException innerException) {
+                vmInstanceCleanup(context, name);
+            } catch (Exception innerException) {
                 e.addSuppressed(innerException);
             }
             throw e;
@@ -544,8 +544,8 @@
         } catch (VirtualMachineException | RuntimeException e) {
             // If anything goes wrong, delete any files created so far and the VM's directory
             try {
-                deleteRecursively(vmDir);
-            } catch (IOException innerException) {
+                vmInstanceCleanup(context, name);
+            } catch (Exception innerException) {
                 e.addSuppressed(innerException);
             }
             throw e;
@@ -587,18 +587,35 @@
             // if a new VM is created with the same name (and files) that's unrelated.
             mWasDeleted = true;
         }
-        // TODO(b/294177871): Request deletion of VM secrets.
-        deleteVmDirectory(context, name);
+        vmInstanceCleanup(context, name);
     }
 
-    static void deleteVmDirectory(Context context, String name) throws VirtualMachineException {
+    // Delete the full VM directory and notify VirtualizationService to remove this
+    // VM instance for housekeeping.
+    @GuardedBy("VirtualMachineManager.sCreateLock")
+    static void vmInstanceCleanup(Context context, String name) throws VirtualMachineException {
+        File vmDir = getVmDir(context, name);
+        notifyInstanceRemoval(vmDir, VirtualizationService.getInstance());
         try {
-            deleteRecursively(getVmDir(context, name));
+            deleteRecursively(vmDir);
         } catch (IOException e) {
             throw new VirtualMachineException(e);
         }
     }
 
+    private static void notifyInstanceRemoval(
+            File vmDirectory, @NonNull VirtualizationService service) {
+        File instanceIdFile = new File(vmDirectory, INSTANCE_ID_FILE);
+        try {
+            byte[] instanceId = Files.readAllBytes(instanceIdFile.toPath());
+            service.getBinder().removeVmInstance(instanceId);
+        } catch (Exception e) {
+            // Deliberately ignoring error in removing VM instance. This potentially leads to
+            // unaccounted instances in the VS' database. But, nothing much can be done by caller.
+            Log.w(TAG, "Failed to notify VS to remove the VM instance", e);
+        }
+    }
+
     // Claim the instance. This notifies the global VS about the ownership of this
     // instance_id for housekeeping purpose.
     void claimInstance() throws VirtualMachineException {
diff --git a/java/framework/src/android/system/virtualmachine/VirtualMachineManager.java b/java/framework/src/android/system/virtualmachine/VirtualMachineManager.java
index 0b9b629..8c0c20e 100644
--- a/java/framework/src/android/system/virtualmachine/VirtualMachineManager.java
+++ b/java/framework/src/android/system/virtualmachine/VirtualMachineManager.java
@@ -335,7 +335,7 @@
         synchronized (sCreateLock) {
             VirtualMachine vm = getVmByName(name);
             if (vm == null) {
-                VirtualMachine.deleteVmDirectory(mContext, name);
+                VirtualMachine.vmInstanceCleanup(mContext, name);
             } else {
                 vm.delete(mContext, name);
             }
diff --git a/virtualizationmanager/src/aidl.rs b/virtualizationmanager/src/aidl.rs
index a9ccd88..b712ed6 100644
--- a/virtualizationmanager/src/aidl.rs
+++ b/virtualizationmanager/src/aidl.rs
@@ -328,6 +328,11 @@
         Ok(is_secretkeeper_supported())
     }
 
+    fn removeVmInstance(&self, instance_id: &[u8; 64]) -> binder::Result<()> {
+        check_manage_access()?;
+        GLOBAL_SERVICE.removeVmInstance(instance_id)
+    }
+
     fn claimVmInstance(&self, instance_id: &[u8; 64]) -> binder::Result<()> {
         check_manage_access()?;
         GLOBAL_SERVICE.claimVmInstance(instance_id)
diff --git a/virtualizationservice/aidl/android/system/virtualizationservice/IVirtualizationService.aidl b/virtualizationservice/aidl/android/system/virtualizationservice/IVirtualizationService.aidl
index ab821a9..f8b5087 100644
--- a/virtualizationservice/aidl/android/system/virtualizationservice/IVirtualizationService.aidl
+++ b/virtualizationservice/aidl/android/system/virtualizationservice/IVirtualizationService.aidl
@@ -100,6 +100,13 @@
     boolean isUpdatableVmSupported();
 
     /**
+     * Notification that state associated with a VM should be removed.
+     *
+     * @param instanceId The ID for the VM.
+     */
+    void removeVmInstance(in byte[64] instanceId);
+
+    /**
      * Notification that ownership of a VM has been claimed by the caller.  Note that no permission
      * checks (with respect to the previous owner) are performed.
      *