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,