diff --git a/demo/java/com/android/microdroid/demo/MainActivity.java b/demo/java/com/android/microdroid/demo/MainActivity.java
index b52ef40..df6f44e 100644
--- a/demo/java/com/android/microdroid/demo/MainActivity.java
+++ b/demo/java/com/android/microdroid/demo/MainActivity.java
@@ -145,6 +145,7 @@
 
     /** Models a virtual machine and outputs from it. */
     public static class VirtualMachineModel extends AndroidViewModel {
+        private static final String VM_NAME = "demo_vm";
         private VirtualMachine mVirtualMachine;
         private final MutableLiveData<String> mConsoleOutput = new MutableLiveData<>();
         private final MutableLiveData<String> mLogOutput = new MutableLiveData<>();
@@ -266,12 +267,12 @@
                 }
                 VirtualMachineConfig config = builder.build();
                 VirtualMachineManager vmm = VirtualMachineManager.getInstance(getApplication());
-                mVirtualMachine = vmm.getOrCreate("demo_vm", config);
+                mVirtualMachine = vmm.getOrCreate(VM_NAME, config);
                 try {
                     mVirtualMachine.setConfig(config);
                 } catch (VirtualMachineException e) {
-                    mVirtualMachine.delete();
-                    mVirtualMachine = vmm.create("demo_vm", config);
+                    vmm.delete(VM_NAME);
+                    mVirtualMachine = vmm.create(VM_NAME, config);
                 }
                 mVirtualMachine.run();
                 mVirtualMachine.setCallback(Executors.newSingleThreadExecutor(), callback);
diff --git a/javalib/src/android/system/virtualmachine/VirtualMachine.java b/javalib/src/android/system/virtualmachine/VirtualMachine.java
index 9a29218..f3e4fe9 100644
--- a/javalib/src/android/system/virtualmachine/VirtualMachine.java
+++ b/javalib/src/android/system/virtualmachine/VirtualMachine.java
@@ -77,7 +77,11 @@
 import java.lang.annotation.RetentionPolicy;
 import java.lang.ref.WeakReference;
 import java.nio.file.FileAlreadyExistsException;
+import java.nio.file.FileVisitResult;
 import java.nio.file.Files;
+import java.nio.file.Path;
+import java.nio.file.SimpleFileVisitor;
+import java.nio.file.attribute.BasicFileAttributes;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.HashMap;
@@ -235,10 +239,9 @@
         mPackageName = context.getPackageName();
         mName = requireNonNull(name, "Name must not be null");
         mConfig = requireNonNull(config, "Config must not be null");
-        mConfigFilePath = getConfigFilePath(context, name);
 
-        final File vmRoot = new File(context.getFilesDir(), VM_DIR);
-        final File thisVmDir = new File(vmRoot, mName);
+        File thisVmDir = getVmDir(context, mName);
+        mConfigFilePath = new File(thisVmDir, CONFIG_FILE);
         mInstanceFilePath = new File(thisVmDir, INSTANCE_IMAGE_FILE);
         mIdsigFilePath = new File(thisVmDir, IDSIG_FILE);
         mExtraApks = setupExtraApks(context, config, thisVmDir);
@@ -315,15 +318,17 @@
     @Nullable
     static VirtualMachine load(
             @NonNull Context context, @NonNull String name) throws VirtualMachineException {
-        File configFilePath = getConfigFilePath(context, name);
+        File thisVmDir = getVmDir(context, name);
+        if (!thisVmDir.exists()) {
+            // The VM doesn't exist.
+            return null;
+        }
+        File configFilePath = new File(thisVmDir, CONFIG_FILE);
         VirtualMachineConfig config;
         try (FileInputStream input = new FileInputStream(configFilePath)) {
             config = VirtualMachineConfig.from(input);
-        } catch (FileNotFoundException e) {
-            // The VM doesn't exist.
-            return null;
         } catch (IOException e) {
-            throw new VirtualMachineException(e);
+            throw new VirtualMachineException("Failed to read config file", e);
         }
 
         VirtualMachine vm = null;
@@ -345,9 +350,6 @@
             }
         }
 
-        // If config file exists, but the instance image file doesn't, it means that the VM is
-        // corrupted. That's different from the case that the VM doesn't exist. Throw an exception
-        // instead of returning null.
         if (!vm.mInstanceFilePath.exists()) {
             throw new VirtualMachineException("instance image missing");
         }
@@ -706,34 +708,54 @@
         stop();
     }
 
-    /**
-     * Deletes this virtual machine. Deleting a virtual machine means deleting any persisted data
-     * associated with it including the per-VM secret. This is an irreversible action. A virtual
-     * machine once deleted can never be restored. A new virtual machine created with the same name
-     * and the same config is different from an already deleted virtual machine.
-     *
-     * @throws VirtualMachineException if the virtual machine is not stopped.
-     * @hide
-     */
-    public void delete() throws VirtualMachineException {
-        if (getStatus() != STATUS_STOPPED) {
+    static void delete(Context context, String name) throws VirtualMachineException {
+        VirtualMachine vm;
+        synchronized (sInstancesLock) {
+            Map<String, WeakReference<VirtualMachine>> instancesMap = sInstances.get(context);
+            if (instancesMap != null && instancesMap.containsKey(name)) {
+                vm = instancesMap.get(name).get();
+            } else {
+                vm = null;
+            }
+        }
+
+        if (vm != null && vm.getStatus() != STATUS_STOPPED) {
             throw new VirtualMachineException("Virtual machine is not stopped");
         }
-        final File vmRootDir = mConfigFilePath.getParentFile();
-        for (ExtraApkSpec extraApks : mExtraApks) {
-            extraApks.idsig.delete();
+
+        try {
+            deleteRecursively(getVmDir(context, name));
+        } catch (IOException e) {
+            throw new VirtualMachineException(e);
         }
-        mConfigFilePath.delete();
-        mInstanceFilePath.delete();
-        mIdsigFilePath.delete();
-        vmRootDir.delete();
 
         synchronized (sInstancesLock) {
-            Map<String, WeakReference<VirtualMachine>> instancesMap = sInstances.get(mContext);
-            if (instancesMap != null) instancesMap.remove(mName);
+            Map<String, WeakReference<VirtualMachine>> instancesMap = sInstances.get(context);
+            if (instancesMap != null) instancesMap.remove(name);
         }
     }
 
+    private static void deleteRecursively(File dir) throws IOException {
+        // Note: This doesn't follow symlinks, which is important. Instead they are just deleted
+        // (and Files.delete deletes the link not the target).
+        Files.walkFileTree(dir.toPath(), new SimpleFileVisitor<>() {
+            @Override
+            public FileVisitResult visitFile(Path file, BasicFileAttributes attrs)
+                    throws IOException {
+                Files.delete(file);
+                return FileVisitResult.CONTINUE;
+            }
+
+            @Override
+            public FileVisitResult postVisitDirectory(Path dir, IOException e) throws IOException {
+                // Directory is deleted after we've visited (deleted) all its contents, so it
+                // should be empty by now.
+                Files.delete(dir);
+                return FileVisitResult.CONTINUE;
+            }
+        });
+    }
+
     /**
      * Returns the CID of this virtual machine, if it is running.
      *
@@ -926,9 +948,9 @@
         }
     }
 
-    private static File getConfigFilePath(@NonNull Context context, @NonNull String name) {
-        final File vmRoot = new File(context.getFilesDir(), VM_DIR);
-        final File thisVmDir = new File(vmRoot, name);
-        return new File(thisVmDir, CONFIG_FILE);
+    @NonNull
+    private static File getVmDir(Context context, String name) {
+        File vmRoot = new File(context.getDataDir(), VM_DIR);
+        return new File(vmRoot, name);
     }
 }
diff --git a/javalib/src/android/system/virtualmachine/VirtualMachineManager.java b/javalib/src/android/system/virtualmachine/VirtualMachineManager.java
index a153e26..f2b7802 100644
--- a/javalib/src/android/system/virtualmachine/VirtualMachineManager.java
+++ b/javalib/src/android/system/virtualmachine/VirtualMachineManager.java
@@ -145,7 +145,8 @@
      * Returns an existing {@link VirtualMachine} with the given name. Returns null if there is no
      * such virtual machine.
      *
-     * @throws VirtualMachineException if the virtual machine could not be successfully retrieved.
+     * @throws VirtualMachineException if the virtual machine exists but could not be successfully
+     *                                 retrieved.
      * @hide
      */
     @Nullable
@@ -173,4 +174,20 @@
         }
         return vm;
     }
+
+    /**
+     * Deletes an existing {@link VirtualMachine}. Deleting a virtual machine means deleting any
+     * persisted data associated with it including the per-VM secret. This is an irreversible
+     * action. A virtual machine once deleted can never be restored. A new virtual machine created
+     * with the same name is different from an already deleted virtual machine even if it has the
+     * same config.
+     *
+     * @throws VirtualMachineException if the virtual machine does not exist, is not stopped,
+     *                                 or cannot be deleted.
+     * @hide
+     */
+    public void delete(@NonNull String name) throws VirtualMachineException {
+        requireNonNull(name);
+        VirtualMachine.delete(mContext, name);
+    }
 }
diff --git a/tests/helper/src/java/com/android/microdroid/test/device/MicrodroidDeviceTestBase.java b/tests/helper/src/java/com/android/microdroid/test/device/MicrodroidDeviceTestBase.java
index 66cd211..ede838b 100644
--- a/tests/helper/src/java/com/android/microdroid/test/device/MicrodroidDeviceTestBase.java
+++ b/tests/helper/src/java/com/android/microdroid/test/device/MicrodroidDeviceTestBase.java
@@ -106,7 +106,7 @@
                 throws VirtualMachineException {
             VirtualMachine existingVm = mVmm.get(name);
             if (existingVm != null) {
-                existingVm.delete();
+                mVmm.delete(name);
             }
             return mVmm.create(name, config);
         }
diff --git a/tests/testapk/src/java/com/android/microdroid/test/MicrodroidTests.java b/tests/testapk/src/java/com/android/microdroid/test/MicrodroidTests.java
index e5052bf..42c0e64 100644
--- a/tests/testapk/src/java/com/android/microdroid/test/MicrodroidTests.java
+++ b/tests/testapk/src/java/com/android/microdroid/test/MicrodroidTests.java
@@ -31,6 +31,8 @@
 import android.system.virtualmachine.VirtualMachine;
 import android.system.virtualmachine.VirtualMachineCallback;
 import android.system.virtualmachine.VirtualMachineConfig;
+import android.system.virtualmachine.VirtualMachineException;
+import android.system.virtualmachine.VirtualMachineManager;
 import android.util.Log;
 
 import com.android.compatibility.common.util.CddTest;
@@ -104,7 +106,7 @@
                 .setPayloadBinaryPath("MicrodroidTestNativeLib.so")
                 .setMemoryMib(minMemoryRequired())
                 .build();
-        VirtualMachine vm = mInner.forceCreateNewVirtualMachine("test_vm_extra_apk", config);
+        VirtualMachine vm = mInner.forceCreateNewVirtualMachine("test_vm", config);
 
         TestResults testResults = runVmTestService(vm);
         assertThat(testResults.mException).isNull();
@@ -162,6 +164,33 @@
     @CddTest(requirements = {
             "9.17/C-1-1",
     })
+    public void deleteVm() throws Exception {
+        assumeSupportedKernel();
+
+        VirtualMachineConfig config = mInner.newVmConfigBuilder()
+                .setPayloadBinaryPath("MicrodroidTestNativeLib.so")
+                .setMemoryMib(minMemoryRequired())
+                .build();
+
+        VirtualMachine vm = mInner.forceCreateNewVirtualMachine("test_vm_delete",
+                config);
+        VirtualMachineManager vmm = mInner.getVirtualMachineManager();
+        vmm.delete("test_vm_delete");
+
+        // VM should no longer exist
+        assertThat(vmm.get("test_vm_delete")).isNull();
+
+        // Can't start the VM even with an existing reference
+        assertThrows(VirtualMachineException.class, vm::run);
+
+        // Can't delete the VM since it no longer exists
+        assertThrows(VirtualMachineException.class, () -> vmm.delete("test_vm_delete"));
+    }
+
+    @Test
+    @CddTest(requirements = {
+            "9.17/C-1-1",
+    })
     public void validApkPathIsAccepted() throws Exception {
         assumeSupportedKernel();
 
@@ -260,7 +289,7 @@
         // Try to run the VM again with the previous instance.img
         // We need to make sure that no changes on config don't invalidate the identity, to compare
         // the result with the below "different debug level" test.
-        File vmRoot = new File(getContext().getFilesDir(), "vm");
+        File vmRoot = new File(getContext().getDataDir(), "vm");
         File vmInstance = new File(new File(vmRoot, "test_vm"), "instance.img");
         File vmInstanceBackup = File.createTempFile("instance", ".img");
         Files.copy(vmInstance.toPath(), vmInstanceBackup.toPath(), REPLACE_EXISTING);
@@ -448,7 +477,7 @@
         mInner.forceCreateNewVirtualMachine(vmName, config);
         assertThat(tryBootVm(TAG, vmName).payloadStarted).isTrue();
 
-        File vmRoot = new File(getContext().getFilesDir(), "vm");
+        File vmRoot = new File(getContext().getDataDir(), "vm");
         File vmDir = new File(vmRoot, vmName);
         File instanceImgPath = new File(vmDir, "instance.img");
         return new RandomAccessFile(instanceImgPath, "rw");