diff --git a/virtualizationservice/Android.bp b/virtualizationservice/Android.bp
index 8b9d0fa..54b32ec 100644
--- a/virtualizationservice/Android.bp
+++ b/virtualizationservice/Android.bp
@@ -34,6 +34,7 @@
         "libmicrodroid_metadata",
         "libmicrodroid_payload_config",
         "libonce_cell",
+        "librustutils",
         "libserde_json",
         "libserde_xml_rs",
         "libserde",
diff --git a/virtualizationservice/src/aidl.rs b/virtualizationservice/src/aidl.rs
index 449103e..6679da6 100644
--- a/virtualizationservice/src/aidl.rs
+++ b/virtualizationservice/src/aidl.rs
@@ -17,7 +17,7 @@
 use crate::composite::make_composite_image;
 use crate::crosvm::{CrosvmConfig, DiskFile, PayloadState, VmInstance, VmState};
 use crate::payload::add_microdroid_images;
-use crate::{Cid, FIRST_GUEST_CID};
+use crate::{Cid, FIRST_GUEST_CID, SYSPROP_LAST_CID};
 
 use android_os_permissions_aidl::aidl::android::os::IPermissionController;
 use android_system_virtualizationservice::aidl::android::system::virtualizationservice::IVirtualMachine::{
@@ -40,12 +40,13 @@
 use android_system_virtualmachineservice::aidl::android::system::virtualmachineservice::IVirtualMachineService::{
     VM_BINDER_SERVICE_PORT, VM_STREAM_SERVICE_PORT, BnVirtualMachineService, IVirtualMachineService,
 };
-use anyhow::{bail, Context, Result};
+use anyhow::{anyhow, bail, Context, Result};
 use ::binder::unstable_api::AsNative;
 use disk::QcowFile;
 use idsig::{V4Signature, HashAlgorithm};
 use log::{debug, error, warn, info};
 use microdroid_payload_config::VmPayloadConfig;
+use rustutils::system_properties;
 use std::convert::TryInto;
 use std::ffi::CString;
 use std::fs::{File, OpenOptions, create_dir};
@@ -100,7 +101,7 @@
         let requester_uid = ThreadState::get_calling_uid();
         let requester_sid = get_calling_sid()?;
         let requester_debug_pid = ThreadState::get_calling_pid();
-        let cid = state.allocate_cid()?;
+        let cid = next_cid().or(Err(ExceptionCode::ILLEGAL_STATE))?;
 
         // Counter to generate unique IDs for temporary image files.
         let mut next_temporary_image_id = 0;
@@ -678,9 +679,6 @@
 /// struct.
 #[derive(Debug)]
 struct State {
-    /// The next available unused CID.
-    next_cid: Cid,
-
     /// The VMs which have been started. When VMs are started a weak reference is added to this list
     /// while a strong reference is returned to the caller over Binder. Once all copies of the
     /// Binder client are dropped the weak reference here will become invalid, and will be removed
@@ -731,22 +729,35 @@
         }
         Some(vm)
     }
-
-    /// Get the next available CID, or an error if we have run out.
-    fn allocate_cid(&mut self) -> binder::Result<Cid> {
-        // TODO(qwandor): keep track of which CIDs are currently in use so that we can reuse them.
-        let cid = self.next_cid;
-        self.next_cid = self.next_cid.checked_add(1).ok_or(ExceptionCode::ILLEGAL_STATE)?;
-        Ok(cid)
-    }
 }
 
 impl Default for State {
     fn default() -> Self {
-        State { next_cid: FIRST_GUEST_CID, vms: vec![], debug_held_vms: vec![] }
+        State { vms: vec![], debug_held_vms: vec![] }
     }
 }
 
+/// Get the next available CID, or an error if we have run out. The last CID used is stored in
+/// a system property so that restart of virtualizationservice doesn't reuse CID while the host
+/// Android is up.
+fn next_cid() -> Result<Cid> {
+    let next = if let Ok(val) = system_properties::read(SYSPROP_LAST_CID) {
+        if let Ok(num) = val.parse::<u32>() {
+            num.checked_add(1).ok_or_else(|| anyhow!("run out of CID"))?
+        } else {
+            error!("Invalid last CID {}. Using {}", &val, FIRST_GUEST_CID);
+            FIRST_GUEST_CID
+        }
+    } else {
+        // First VM since the boot
+        FIRST_GUEST_CID
+    };
+    // Persist the last value for next use
+    let str_val = format!("{}", next);
+    system_properties::write(SYSPROP_LAST_CID, &str_val)?;
+    Ok(next)
+}
+
 /// Gets the `VirtualMachineState` of the given `VmInstance`.
 fn get_state(instance: &VmInstance) -> VirtualMachineState {
     match &*instance.vm_state.lock().unwrap() {
diff --git a/virtualizationservice/src/main.rs b/virtualizationservice/src/main.rs
index 22ddf08..0e1e974 100644
--- a/virtualizationservice/src/main.rs
+++ b/virtualizationservice/src/main.rs
@@ -30,6 +30,8 @@
 /// are reserved for the host or other usage.
 const FIRST_GUEST_CID: Cid = 10;
 
+const SYSPROP_LAST_CID: &str = "virtualizationservice.state.last_cid";
+
 const LOG_TAG: &str = "VirtualizationService";
 
 /// The unique ID of a VM used (together with a port number) for vsock communication.