diff --git a/java/service/Android.bp b/java/service/Android.bp
index fdfb203..8bac7be 100644
--- a/java/service/Android.bp
+++ b/java/service/Android.bp
@@ -29,6 +29,9 @@
         "framework",
         "services.core",
     ],
+    static_libs: [
+        "android.system.virtualizationmaintenance-java",
+    ],
     sdk_version: "core_platform",
     apex_available: ["com.android.virt"],
     installable: true,
diff --git a/java/service/src/com/android/system/virtualmachine/VirtualizationSystemService.java b/java/service/src/com/android/system/virtualmachine/VirtualizationSystemService.java
index 2905acd..3f973b4 100644
--- a/java/service/src/com/android/system/virtualmachine/VirtualizationSystemService.java
+++ b/java/service/src/com/android/system/virtualmachine/VirtualizationSystemService.java
@@ -16,16 +16,121 @@
 
 package com.android.system.virtualmachine;
 
+import android.content.BroadcastReceiver;
 import android.content.Context;
+import android.content.Intent;
+import android.content.IntentFilter;
+import android.os.Handler;
+import android.os.IBinder;
+import android.os.ServiceManager;
+import android.os.UserHandle;
+import android.system.virtualizationmaintenance.IVirtualizationMaintenance;
+import android.util.Log;
+
+import com.android.internal.os.BackgroundThread;
 import com.android.server.SystemService;
 
-/** TODO */
+/**
+ * This class exists to notify virtualization service of relevant things happening in the Android
+ * framework.
+ *
+ * <p>It currently is responsible for Secretkeeper-related maintenance - ensuring that we are not
+ * storing secrets for apps or users that no longer exist.
+ */
 public class VirtualizationSystemService extends SystemService {
+    private static final String TAG = VirtualizationSystemService.class.getName();
+    private static final String SERVICE_NAME = "android.system.virtualizationmaintenance";
+    private Handler mHandler;
 
     public VirtualizationSystemService(Context context) {
         super(context);
     }
 
     @Override
-    public void onStart() {}
+    public void onStart() {
+        // Nothing needed here - we don't expose any binder service. The binder service we use is
+        // exposed as a lazy service by the virtualizationservice native binary.
+    }
+
+    @Override
+    public void onBootPhase(int phase) {
+        if (phase != PHASE_BOOT_COMPLETED) return;
+
+        mHandler = BackgroundThread.getHandler();
+        new Receiver().registerForBroadcasts();
+    }
+
+    private void notifyAppRemoved(int uid) {
+        try {
+            IVirtualizationMaintenance maintenance = connectToMaintenanceService();
+            maintenance.appRemoved(UserHandle.getUserId(uid), UserHandle.getAppId(uid));
+        } catch (Exception e) {
+            Log.e(TAG, "notifyAppRemoved failed", e);
+        }
+    }
+
+    private void notifyUserRemoved(int userId) {
+        try {
+            IVirtualizationMaintenance maintenance = connectToMaintenanceService();
+            maintenance.userRemoved(userId);
+        } catch (Exception e) {
+            Log.e(TAG, "notifyUserRemoved failed", e);
+        }
+    }
+
+    private static IVirtualizationMaintenance connectToMaintenanceService() {
+        IBinder binder = ServiceManager.waitForService(SERVICE_NAME);
+        IVirtualizationMaintenance maintenance =
+                IVirtualizationMaintenance.Stub.asInterface(binder);
+        if (maintenance == null) {
+            throw new IllegalStateException("Failed to connect to " + SERVICE_NAME);
+        }
+        return maintenance;
+    }
+
+    private class Receiver extends BroadcastReceiver {
+        public void registerForBroadcasts() {
+            Context allUsers = getContext().createContextAsUser(UserHandle.ALL, 0 /* flags */);
+
+            allUsers.registerReceiver(this, new IntentFilter(Intent.ACTION_USER_REMOVED));
+
+            IntentFilter packageFilter = new IntentFilter(Intent.ACTION_PACKAGE_REMOVED);
+            packageFilter.addDataScheme("package");
+            allUsers.registerReceiver(this, packageFilter);
+        }
+
+        @Override
+        public void onReceive(Context context, Intent intent) {
+            switch (intent.getAction()) {
+                case Intent.ACTION_USER_REMOVED:
+                    onUserRemoved(intent);
+                    break;
+                case Intent.ACTION_PACKAGE_REMOVED:
+                    onPackageRemoved(intent);
+                    break;
+                default:
+                    Log.e(TAG, "received unexpected intent: " + intent.getAction());
+                    break;
+            }
+        }
+
+        private void onUserRemoved(Intent intent) {
+            int userId = intent.getIntExtra(Intent.EXTRA_USER_HANDLE, UserHandle.USER_NULL);
+            if (userId != UserHandle.USER_NULL) {
+                mHandler.post(() -> notifyUserRemoved(userId));
+            }
+        }
+
+        private void onPackageRemoved(Intent intent) {
+            if (intent.getBooleanExtra(Intent.EXTRA_REPLACING, false)
+                    || !intent.getBooleanExtra(Intent.EXTRA_DATA_REMOVED, false)) {
+                // Package is being updated rather than uninstalled.
+                return;
+            }
+            int uid = intent.getIntExtra(Intent.EXTRA_UID, -1);
+            if (uid != -1) {
+                mHandler.post(() -> notifyAppRemoved(uid));
+            }
+        }
+    }
 }
diff --git a/virtualizationservice/aidl/Android.bp b/virtualizationservice/aidl/Android.bp
index 66de092..112e1cc 100644
--- a/virtualizationservice/aidl/Android.bp
+++ b/virtualizationservice/aidl/Android.bp
@@ -61,6 +61,9 @@
     backend: {
         java: {
             sdk_version: "module_current",
+            apex_available: [
+                "com.android.virt",
+            ],
         },
         rust: {
             enabled: true,