diff --git a/guest/microdroid_manager/aidl/android/system/virtualization/payload/IVmPayloadService.aidl b/guest/microdroid_manager/aidl/android/system/virtualization/payload/IVmPayloadService.aidl
index 30c4299..8d02d97 100644
--- a/guest/microdroid_manager/aidl/android/system/virtualization/payload/IVmPayloadService.aidl
+++ b/guest/microdroid_manager/aidl/android/system/virtualization/payload/IVmPayloadService.aidl
@@ -130,4 +130,13 @@
      *         certification chain.
      */
     AttestationResult requestAttestation(in byte[] challenge, in boolean testMode);
+
+    /**
+     * Checks whether the VM instance is new - i.e., if this is the first run of an instance.
+     * This is an indication of fresh new VM secrets. Payload can use this to setup the fresh
+     * instance if needed.
+     *
+     * @return true on the first boot of the instance & false on subsequent boot.
+     */
+    boolean isNewInstance();
 }
diff --git a/guest/microdroid_manager/src/main.rs b/guest/microdroid_manager/src/main.rs
index 451c3c8..57ad35d 100644
--- a/guest/microdroid_manager/src/main.rs
+++ b/guest/microdroid_manager/src/main.rs
@@ -250,7 +250,7 @@
 
     if is_strict_boot() {
         // Provisioning must happen on the first boot and never again.
-        if is_new_instance() {
+        if is_new_instance_legacy() {
             ensure!(
                 saved_data.is_none(),
                 MicrodroidError::PayloadInvalidConfig(
@@ -297,6 +297,17 @@
     Ok(instance_data)
 }
 
+// The VM instance run can be
+// 1. Either Newly created - which can happen if this is really a new VM instance (or a malicious
+//    Android has deleted relevant secrets)
+// 2. Or Re-run from an already seen VM instance.
+#[derive(PartialEq, Eq)]
+enum VmInstanceState {
+    Unknown,
+    NewlyCreated,
+    PreviouslySeen,
+}
+
 fn try_run_payload(
     service: &Strong<dyn IVirtualMachineService>,
     vm_payload_service_fd: OwnedFd,
@@ -326,8 +337,25 @@
     // To minimize the exposure to untrusted data, derive dice profile as soon as possible.
     info!("DICE derivation for payload");
     let dice_artifacts = dice_derivation(dice, &instance_data, &payload_metadata)?;
-    let vm_secret =
-        VmSecret::new(dice_artifacts, service).context("Failed to create VM secrets")?;
+    let mut state = VmInstanceState::Unknown;
+    let vm_secret = VmSecret::new(dice_artifacts, service, &mut state)
+        .context("Failed to create VM secrets")?;
+
+    let is_new_instance = match state {
+        VmInstanceState::NewlyCreated => true,
+        VmInstanceState::PreviouslySeen => false,
+        VmInstanceState::Unknown => {
+            // VmSecret instantiation was not able to determine the state. This should only happen
+            // for legacy secret mechanism (V1) - in which case fallback to legacy
+            // instance.img based determination of state.
+            ensure!(
+                !should_defer_rollback_protection(),
+                "VmInstanceState is Unknown whilst guest is expected to use V2 based secrets.
+                This should've never happened"
+            );
+            is_new_instance_legacy()
+        }
+    };
 
     if cfg!(dice_changes) {
         // Now that the DICE derivation is done, it's ok to allow payload code to run.
@@ -387,6 +415,7 @@
         service.clone(),
         vm_secret,
         vm_payload_service_fd,
+        is_new_instance,
     )?;
 
     // Set export_tombstones if enabled
@@ -488,7 +517,7 @@
     Path::new(AVF_STRICT_BOOT).exists()
 }
 
-fn is_new_instance() -> bool {
+fn is_new_instance_legacy() -> bool {
     Path::new(AVF_NEW_INSTANCE).exists()
 }
 
diff --git a/guest/microdroid_manager/src/vm_payload_service.rs b/guest/microdroid_manager/src/vm_payload_service.rs
index c4a9111..fb57812 100644
--- a/guest/microdroid_manager/src/vm_payload_service.rs
+++ b/guest/microdroid_manager/src/vm_payload_service.rs
@@ -33,6 +33,7 @@
     allow_restricted_apis: bool,
     virtual_machine_service: Strong<dyn IVirtualMachineService>,
     secret: VmSecret,
+    is_new_instance: bool,
 }
 
 impl IVmPayloadService for VmPayloadService {
@@ -116,6 +117,10 @@
             .or_service_specific_exception(-1)?;
         Ok(())
     }
+
+    fn isNewInstance(&self) -> binder::Result<bool> {
+        Ok(self.is_new_instance)
+    }
 }
 
 impl Interface for VmPayloadService {}
@@ -126,8 +131,9 @@
         allow_restricted_apis: bool,
         vm_service: Strong<dyn IVirtualMachineService>,
         secret: VmSecret,
+        is_new_instance: bool,
     ) -> VmPayloadService {
-        Self { allow_restricted_apis, virtual_machine_service: vm_service, secret }
+        Self { allow_restricted_apis, virtual_machine_service: vm_service, secret, is_new_instance }
     }
 
     fn check_restricted_apis_allowed(&self) -> binder::Result<()> {
@@ -147,9 +153,10 @@
     vm_service: Strong<dyn IVirtualMachineService>,
     secret: VmSecret,
     vm_payload_service_fd: OwnedFd,
+    is_new_instance: bool,
 ) -> Result<()> {
     let vm_payload_binder = BnVmPayloadService::new_binder(
-        VmPayloadService::new(allow_restricted_apis, vm_service, secret),
+        VmPayloadService::new(allow_restricted_apis, vm_service, secret, is_new_instance),
         BinderFeatures::default(),
     );
 
diff --git a/guest/microdroid_manager/src/vm_secret.rs b/guest/microdroid_manager/src/vm_secret.rs
index 04d6817..56b3482 100644
--- a/guest/microdroid_manager/src/vm_secret.rs
+++ b/guest/microdroid_manager/src/vm_secret.rs
@@ -38,6 +38,7 @@
 use zeroize::Zeroizing;
 use std::sync::Mutex;
 use std::sync::Arc;
+use crate::VmInstanceState;
 
 const ENCRYPTEDSTORE_KEY_IDENTIFIER: &str = "encryptedstore_key";
 const AUTHORITY_HASH: i64 = -4670549;
@@ -99,6 +100,7 @@
     pub fn new(
         dice_artifacts: OwnedDiceArtifacts,
         vm_service: &Strong<dyn IVirtualMachineService>,
+        state: &mut VmInstanceState,
     ) -> Result<Self> {
         ensure!(dice_artifacts.bcc().is_some(), "Dice chain missing");
         if !crate::should_defer_rollback_protection() {
@@ -116,11 +118,13 @@
         let session = SkVmSession::new(vm_service, &explicit_dice, policy)?;
         let mut skp_secret = Zeroizing::new([0u8; SECRET_SIZE]);
         if let Some(secret) = session.get_secret(id)? {
-            *skp_secret = secret
+            *skp_secret = secret;
+            *state = VmInstanceState::PreviouslySeen;
         } else {
             log::warn!("No entry found in Secretkeeper for this VM instance, creating new secret.");
             *skp_secret = rand::random();
             session.store_secret(id, skp_secret.clone())?;
+            *state = VmInstanceState::NewlyCreated;
         }
         Ok(Self::V2 {
             instance_id: id,
diff --git a/libs/libvm_payload/include/vm_payload.h b/libs/libvm_payload/include/vm_payload.h
index 43fba82..e4609fa 100644
--- a/libs/libvm_payload/include/vm_payload.h
+++ b/libs/libvm_payload/include/vm_payload.h
@@ -118,6 +118,11 @@
  * byte sequences and do not need to be kept secret; typically they are
  * hardcoded in the calling code.
  *
+ * The secret is linked to the instance & will be created for a new instance.
+ * Callers should check `AVmPayload_isNewInstance()` to meaningfully use the secret.
+ * For ex, decryption of any old data is meaningless with the returned secret of a new
+ * VM instance with fresh keys.
+ *
  * \param identifier identifier of the secret to return.
  * \param identifier_size size of the secret identifier.
  * \param secret pointer to size bytes where the secret is written.
@@ -304,4 +309,13 @@
 int32_t AVmPayload_readRollbackProtectedSecret(void* _Nullable buf, size_t n) __INTRODUCED_IN(36);
 ;
 
+/**
+ * Checks whether the VM instance is new - i.e., if this is the first run of an instance.
+ * This is an indication of fresh new VM secrets. Payload can use this to setup the fresh
+ * instance if needed.
+ *
+ *  \return true if this is the first run of an instance, false otherwise.
+ */
+bool AVmPayload_isNewInstance() __INTRODUCED_IN(36);
+
 __END_DECLS
diff --git a/libs/libvm_payload/libvm_payload.map.txt b/libs/libvm_payload/libvm_payload.map.txt
index 0c6b56d..ca949d9 100644
--- a/libs/libvm_payload/libvm_payload.map.txt
+++ b/libs/libvm_payload/libvm_payload.map.txt
@@ -17,6 +17,7 @@
     AVmAttestationResult_getCertificateAt; # systemapi introduced=VanillaIceCream
     AVmPayload_writeRollbackProtectedSecret; # systemapi introduced=36
     AVmPayload_readRollbackProtectedSecret; # systemapi introduced=36
+    AVmPayload_isNewInstance;                # systemapi introduced=36
   local:
     *;
 };
diff --git a/libs/libvm_payload/src/lib.rs b/libs/libvm_payload/src/lib.rs
index 29b0cbd..cbadec2 100644
--- a/libs/libvm_payload/src/lib.rs
+++ b/libs/libvm_payload/src/lib.rs
@@ -652,3 +652,15 @@
         .context("Failed to read rollback protected data")?;
     Ok(rp)
 }
+
+/// Checks whether the VM instance is new - i.e., if this is the first run of an instance.
+///
+/// Panics on error (including unexpected server exit).
+#[no_mangle]
+pub extern "C" fn AVmPayload_isNewInstance() -> bool {
+    unwrap_or_abort(try_is_new_instance())
+}
+
+fn try_is_new_instance() -> Result<bool> {
+    get_vm_payload_service()?.isNewInstance().context("Cannot determine if the instance is new")
+}
diff --git a/libs/libvm_payload/wrapper/lib.rs b/libs/libvm_payload/wrapper/lib.rs
index 133b14e..bf274b0 100644
--- a/libs/libvm_payload/wrapper/lib.rs
+++ b/libs/libvm_payload/wrapper/lib.rs
@@ -31,7 +31,7 @@
 use std::ptr;
 use vm_payload_bindgen::{
     AIBinder, AVmPayload_getApkContentsPath, AVmPayload_getEncryptedStoragePath,
-    AVmPayload_getVmInstanceSecret, AVmPayload_notifyPayloadReady,
+    AVmPayload_getVmInstanceSecret, AVmPayload_isNewInstance, AVmPayload_notifyPayloadReady,
     AVmPayload_readRollbackProtectedSecret, AVmPayload_runVsockRpcServer,
     AVmPayload_writeRollbackProtectedSecret,
 };
@@ -208,3 +208,11 @@
     // SAFETY: The function only writes to `[data]` within its bounds.
     unsafe { AVmPayload_writeRollbackProtectedSecret(data.as_ptr() as *const c_void, data.len()) }
 }
+
+/// Checks whether the VM instance is new - i.e., if this is the first run of an instance.
+/// This is an indication of fresh new VM secrets. Payload can use this to setup the fresh
+/// instance if needed.
+pub fn is_new_instance_status() -> bool {
+    // SAFETY: The function returns bool, no arguments are needed.
+    unsafe { AVmPayload_isNewInstance() }
+}
diff --git a/tests/aidl/com/android/microdroid/testservice/ITestService.aidl b/tests/aidl/com/android/microdroid/testservice/ITestService.aidl
index 73e5c5c..6a413d6 100644
--- a/tests/aidl/com/android/microdroid/testservice/ITestService.aidl
+++ b/tests/aidl/com/android/microdroid/testservice/ITestService.aidl
@@ -97,4 +97,11 @@
      * requests in flight to fail.
      */
     oneway void quit();
+
+    /**
+     * Checks whether the VM instance is new - i.e., if this is the first run of an instance.
+     *
+     * @return true on the first boot of the instance & false on subsequent boot.
+     */
+    boolean isNewInstance();
 }
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 b98531d..c05fb0b 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
@@ -615,6 +615,7 @@
         public byte[] mInstanceSecret;
         public int mPageSize;
         public byte[] mPayloadRpData;
+        public boolean mIsNewInstance;
 
         public void assertNoException() {
             if (mException != null) {
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 797214c..a50ce98 100644
--- a/tests/testapk/src/java/com/android/microdroid/test/MicrodroidTests.java
+++ b/tests/testapk/src/java/com/android/microdroid/test/MicrodroidTests.java
@@ -1941,6 +1941,44 @@
 
     @Test
     @CddTest
+    public void isNewInstanceTest() throws Exception {
+        assumeSupportedDevice();
+
+        VirtualMachineConfig config =
+                newVmConfigBuilderWithPayloadBinary("MicrodroidTestNativeLib.so")
+                        .setMemoryBytes(minMemoryRequired())
+                        .setDebugLevel(DEBUG_LEVEL_FULL)
+                        .build();
+        // TODO(b/325094712): Cuttlefish doesn't support device tree overlays which is required to
+        // find if the VM run is a new instance.
+        assumeFalse(
+                "Cuttlefish/Goldfish doesn't support device tree under /proc/device-tree",
+                isCuttlefish() || isGoldfish());
+        VirtualMachine vm = forceCreateNewVirtualMachine("test_vm_a", config);
+        TestResults testResults =
+                runVmTestService(
+                        TAG,
+                        vm,
+                        (ts, tr) -> {
+                            tr.mIsNewInstance = ts.isNewInstance();
+                        });
+        testResults.assertNoException();
+        assertThat(testResults.mIsNewInstance).isTrue();
+
+        // Re-run the same VM & ensure isNewInstance is false.
+        testResults =
+                runVmTestService(
+                        TAG,
+                        vm,
+                        (ts, tr) -> {
+                            tr.mIsNewInstance = ts.isNewInstance();
+                        });
+        testResults.assertNoException();
+        assertThat(testResults.mIsNewInstance).isFalse();
+    }
+
+    @Test
+    @CddTest(requirements = {"9.17/C-1-1", "9.17/C-2-1"})
     public void canReadFileFromAssets_debugFull() throws Exception {
         assumeSupportedDevice();
 
diff --git a/tests/testapk/src/native/testbinary.cpp b/tests/testapk/src/native/testbinary.cpp
index 83b6d23..06c7e9d 100644
--- a/tests/testapk/src/native/testbinary.cpp
+++ b/tests/testapk/src/native/testbinary.cpp
@@ -364,6 +364,11 @@
             return ScopedAStatus::ok();
         }
 
+        ScopedAStatus isNewInstance(bool* is_new_instance_out) override {
+            *is_new_instance_out = AVmPayload_isNewInstance();
+            return ScopedAStatus::ok();
+        }
+
         ScopedAStatus quit() override { exit(0); }
     };
     auto testService = ndk::SharedRefBase::make<TestService>();
diff --git a/tests/testapk/src/native/testbinary.rs b/tests/testapk/src/native/testbinary.rs
index dee3b8e..c9d46b8 100644
--- a/tests/testapk/src/native/testbinary.rs
+++ b/tests/testapk/src/native/testbinary.rs
@@ -132,6 +132,9 @@
     fn insecurelyWritePayloadRpData(&self, _: &[u8; 32]) -> BinderResult<()> {
         unimplemented()
     }
+    fn isNewInstance(&self) -> BinderResult<bool> {
+        unimplemented()
+    }
 }
 
 fn unimplemented<T>() -> BinderResult<T> {
diff --git a/tests/vmshareapp/src/java/com/android/microdroid/test/sharevm/VmShareServiceImpl.java b/tests/vmshareapp/src/java/com/android/microdroid/test/sharevm/VmShareServiceImpl.java
index 4465c5e..1f71888 100644
--- a/tests/vmshareapp/src/java/com/android/microdroid/test/sharevm/VmShareServiceImpl.java
+++ b/tests/vmshareapp/src/java/com/android/microdroid/test/sharevm/VmShareServiceImpl.java
@@ -286,5 +286,10 @@
         public void insecurelyWritePayloadRpData(byte[] data) {
             throw new UnsupportedOperationException("Not supported");
         }
+
+        @Override
+        public boolean isNewInstance() {
+            throw new UnsupportedOperationException("Not supported");
+        }
     }
 }