diff --git a/microdroid_manager/Android.bp b/microdroid_manager/Android.bp
index a082beb..95a7014 100644
--- a/microdroid_manager/Android.bp
+++ b/microdroid_manager/Android.bp
@@ -9,8 +9,12 @@
     edition: "2018",
     prefer_rlib: true,
     rustlibs: [
+        "android.system.virtualizationservice-rust",
+        "android.system.virtualmachineservice-rust",
         "libanyhow",
         "libapkverify",
+        "libbinder_rpc_unstable_bindgen",
+        "libbinder_rs",
         "libkernlog",
         "liblibc",
         "liblog_rust",
@@ -22,6 +26,9 @@
         "libserde_json",
         "libvsock",
     ],
+    shared_libs: [
+        "libbinder_rpc_unstable",
+    ],
     init_rc: ["microdroid_manager.rc"],
 }
 
diff --git a/microdroid_manager/src/main.rs b/microdroid_manager/src/main.rs
index d7e256b..2fb7fdd 100644
--- a/microdroid_manager/src/main.rs
+++ b/microdroid_manager/src/main.rs
@@ -19,6 +19,8 @@
 
 use anyhow::{anyhow, bail, Context, Result};
 use apkverify::verify;
+use binder::unstable_api::{new_spibinder, AIBinder};
+use binder::{FromIBinder, Strong};
 use log::{error, info, warn};
 use microdroid_payload_config::{Task, TaskType, VmPayloadConfig};
 use rustutils::system_properties::PropertyWatcher;
@@ -30,9 +32,35 @@
 use std::time::Duration;
 use vsock::VsockStream;
 
+use android_system_virtualmachineservice::aidl::android::system::virtualmachineservice::IVirtualMachineService::IVirtualMachineService;
+
 const WAIT_TIMEOUT: Duration = Duration::from_secs(10);
 const DM_MOUNTED_APK_PATH: &str = "/dev/block/mapper/microdroid-apk";
 
+/// The CID representing the host VM
+const VMADDR_CID_HOST: u32 = 2;
+
+/// Port number that virtualizationservice listens on connections from the guest VMs for the
+/// VirtualMachineService binder service
+/// Sync with virtualizationservice/src/aidl.rs
+const PORT_VM_BINDER_SERVICE: u32 = 5000;
+
+fn get_vms_rpc_binder() -> Result<Strong<dyn IVirtualMachineService>> {
+    // SAFETY: AIBinder returned by RpcClient has correct reference count, and the ownership can be
+    // safely taken by new_spibinder.
+    let ibinder = unsafe {
+        new_spibinder(binder_rpc_unstable_bindgen::RpcClient(
+            VMADDR_CID_HOST,
+            PORT_VM_BINDER_SERVICE,
+        ) as *mut AIBinder)
+    };
+    if let Some(ibinder) = ibinder {
+        <dyn IVirtualMachineService>::try_from(ibinder).context("Cannot connect to RPC service")
+    } else {
+        bail!("Invalid raw AIBinder")
+    }
+}
+
 fn main() -> Result<()> {
     kernlog::init()?;
     info!("started.");
@@ -44,6 +72,11 @@
         return Err(err);
     }
 
+    // TODO(b/191845268): microdroid_manager should use this binder to communicate with the host
+    if let Err(err) = get_vms_rpc_binder() {
+        error!("cannot connect to VirtualMachineService: {}", err);
+    }
+
     if !metadata.payload_config_path.is_empty() {
         let config = load_config(Path::new(&metadata.payload_config_path))?;
 
diff --git a/virtualizationservice/Android.bp b/virtualizationservice/Android.bp
index c3b36ee..8b9d0fa 100644
--- a/virtualizationservice/Android.bp
+++ b/virtualizationservice/Android.bp
@@ -21,9 +21,12 @@
     prefer_rlib: true,
     rustlibs: [
         "android.system.virtualizationservice-rust",
+        "android.system.virtualmachineservice-rust",
         "android.os.permissions_aidl-rust",
         "libandroid_logger",
         "libanyhow",
+        "libbinder_rpc_unstable_bindgen",
+        "libbinder_rs",
         "libcommand_fds",
         "libdisk",
         "libidsig",
@@ -39,6 +42,9 @@
         "libzip",
         "libvsock",
     ],
+    shared_libs: [
+        "libbinder_rpc_unstable",
+    ],
 }
 
 rust_binary {
diff --git a/virtualizationservice/aidl/Android.bp b/virtualizationservice/aidl/Android.bp
index 7d85bd3..974bdc6 100644
--- a/virtualizationservice/aidl/Android.bp
+++ b/virtualizationservice/aidl/Android.bp
@@ -4,7 +4,7 @@
 
 aidl_interface {
     name: "android.system.virtualizationservice",
-    srcs: ["**/*.aidl"],
+    srcs: ["android/system/virtualizationservice/**/*.aidl"],
     // This is never accessed directly. Apps are expected to use this indirectly via the Java
     // wrapper android.system.virtualmachine.
     unstable: true,
@@ -27,3 +27,15 @@
         },
     },
 }
+
+aidl_interface {
+    name: "android.system.virtualmachineservice",
+    srcs: ["android/system/virtualmachineservice/**/*.aidl"],
+    unstable: true,
+    backend: {
+        rust: {
+            enabled: true,
+            apex_available: ["com.android.virt"],
+        },
+    },
+}
diff --git a/virtualizationservice/aidl/android/system/virtualmachineservice/IVirtualMachineService.aidl b/virtualizationservice/aidl/android/system/virtualmachineservice/IVirtualMachineService.aidl
new file mode 100644
index 0000000..b5cda7d
--- /dev/null
+++ b/virtualizationservice/aidl/android/system/virtualmachineservice/IVirtualMachineService.aidl
@@ -0,0 +1,25 @@
+/*
+ * Copyright 2021 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package android.system.virtualmachineservice;
+
+/** {@hide} */
+interface IVirtualMachineService {
+    /**
+     * Notifies that the virtual machine is ready.
+     * TODO(b/191845268): remove cid parameter
+     */
+    void notifyPayloadStarted(int cid);
+}
diff --git a/virtualizationservice/src/aidl.rs b/virtualizationservice/src/aidl.rs
index 23a9c03..e85ac2c 100644
--- a/virtualizationservice/src/aidl.rs
+++ b/virtualizationservice/src/aidl.rs
@@ -20,8 +20,8 @@
 use crate::{Cid, FIRST_GUEST_CID};
 
 use android_os_permissions_aidl::aidl::android::os::IPermissionController;
-use android_system_virtualizationservice::aidl::android::system::virtualizationservice::IVirtualizationService::IVirtualizationService;
 use android_system_virtualizationservice::aidl::android::system::virtualizationservice::DiskImage::DiskImage;
+use android_system_virtualizationservice::aidl::android::system::virtualizationservice::IVirtualizationService::IVirtualizationService;
 use android_system_virtualizationservice::aidl::android::system::virtualizationservice::IVirtualMachine::{
     BnVirtualMachine, IVirtualMachine,
 };
@@ -35,7 +35,11 @@
 use android_system_virtualizationservice::binder::{
     self, BinderFeatures, ExceptionCode, Interface, ParcelFileDescriptor, Status, Strong, ThreadState,
 };
+use android_system_virtualmachineservice::aidl::android::system::virtualmachineservice::IVirtualMachineService::{
+    BnVirtualMachineService, IVirtualMachineService,
+};
 use anyhow::{bail, Context, Result};
+use ::binder::unstable_api::AsNative;
 use disk::QcowFile;
 use idsig::{V4Signature, HashAlgorithm};
 use log::{debug, error, warn, info};
@@ -63,6 +67,11 @@
 /// payload output
 const PORT_VIRT_SERVICE: u32 = 3000;
 
+/// Port number that virtualizationservice listens on connections from the guest VMs for the
+/// VirtualMachineService binder service
+/// Sync with microdroid_manager/src/main.rs
+const PORT_VM_BINDER_SERVICE: u32 = 5000;
+
 /// The size of zero.img.
 /// Gaps in composite disk images are filled with a shared zero.img.
 const ZERO_FILLER_SIZE: u64 = 4096;
@@ -273,10 +282,34 @@
 impl VirtualizationService {
     pub fn init() -> VirtualizationService {
         let service = VirtualizationService::default();
+
+        // server for payload output
         let state = service.state.clone(); // reference to state (not the state itself) is copied
         std::thread::spawn(move || {
             handle_connection_from_vm(state).unwrap();
         });
+
+        // binder server for vm
+        let state = service.state.clone(); // reference to state (not the state itself) is copied
+        std::thread::spawn(move || {
+            let mut service = VirtualMachineService::new_binder(state).as_binder();
+            debug!("virtual machine service is starting as an RPC service.");
+            // SAFETY: Service ownership is transferring to the server and won't be valid afterward.
+            // Plus the binder objects are threadsafe.
+            let retval = unsafe {
+                binder_rpc_unstable_bindgen::RunRpcServer(
+                    service.as_native_mut() as *mut binder_rpc_unstable_bindgen::AIBinder,
+                    PORT_VM_BINDER_SERVICE,
+                )
+            };
+            if retval {
+                debug!("RPC server has shut down gracefully");
+            } else {
+                bail!("Premature termination of RPC server");
+            }
+
+            Ok(retval)
+        });
         service
     }
 }
@@ -301,6 +334,7 @@
                 warn!("connection is not from a guest VM");
                 continue;
             }
+            // TODO(b/191845268): handle this with VirtualMachineService
             if let Some(vm) = state.lock().unwrap().get_vm(cid) {
                 vm.callbacks.notify_payload_started(cid, stream);
             }
@@ -702,3 +736,35 @@
         }
     }
 }
+
+/// Implementation of `IVirtualMachineService`, the entry point of the AIDL service.
+#[derive(Debug, Default)]
+struct VirtualMachineService {
+    state: Arc<Mutex<State>>,
+}
+
+impl Interface for VirtualMachineService {}
+
+impl IVirtualMachineService for VirtualMachineService {
+    fn notifyPayloadStarted(&self, cid: i32) -> binder::Result<()> {
+        let cid = cid as Cid;
+        if self.state.lock().unwrap().get_vm(cid).is_none() {
+            error!("notifyPayloadStarted is called from an unknown cid {}", cid);
+            return Err(new_binder_exception(
+                ExceptionCode::SERVICE_SPECIFIC,
+                format!("cannot find a VM with cid {}", cid),
+            ));
+        }
+        info!("VM having CID {} started payload", cid);
+        Ok(())
+    }
+}
+
+impl VirtualMachineService {
+    fn new_binder(state: Arc<Mutex<State>>) -> Strong<dyn IVirtualMachineService> {
+        BnVirtualMachineService::new_binder(
+            VirtualMachineService { state },
+            BinderFeatures::default(),
+        )
+    }
+}