diff --git a/compos/Android.bp b/compos/Android.bp
index 783ba22..09d2d8e 100644
--- a/compos/Android.bp
+++ b/compos/Android.bp
@@ -52,6 +52,7 @@
         "libnix",
         "libodsign_proto_rust",
         "libprotobuf",
+        "libregex",
         "libring",
         "libscopeguard",
     ],
diff --git a/compos/aidl/com/android/compos/ICompOsService.aidl b/compos/aidl/com/android/compos/ICompOsService.aidl
index ad37806..1a28a18 100644
--- a/compos/aidl/com/android/compos/ICompOsService.aidl
+++ b/compos/aidl/com/android/compos/ICompOsService.aidl
@@ -33,15 +33,6 @@
     void initializeSigningKey(in byte[] keyBlob);
 
     /**
-     * Initializes the classpaths necessary for preparing and running compilation.
-     *
-     * TODO(198211396): Implement properly. We can't simply accepting the classpaths from Android
-     * since they are not derived from staged APEX (besides security reasons).
-     */
-    void initializeClasspaths(String bootClasspath, String dex2oatBootClasspath,
-            String systemServerClasspath, String standaloneSystemServerJars);
-
-    /**
      * Run odrefresh in the VM context.
      *
      * The execution is based on the VM's APEX mounts, files on Android's /system (by accessing
diff --git a/compos/apk/assets/vm_config.json b/compos/apk/assets/vm_config.json
index d008c12..0e97228 100644
--- a/compos/apk/assets/vm_config.json
+++ b/compos/apk/assets/vm_config.json
@@ -18,7 +18,10 @@
       "name": "com.android.compos"
     },
     {
+      "name": "com.android.sdkext"
+    },
+    {
       "name": "{CLASSPATH}"
     }
   ]
-}
\ No newline at end of file
+}
diff --git a/compos/apk/assets/vm_config_staged.json b/compos/apk/assets/vm_config_staged.json
index e42ebe0..5820982 100644
--- a/compos/apk/assets/vm_config_staged.json
+++ b/compos/apk/assets/vm_config_staged.json
@@ -19,7 +19,10 @@
       "name": "com.android.compos"
     },
     {
+      "name": "com.android.sdkext"
+    },
+    {
       "name": "{CLASSPATH}"
     }
   ]
-}
\ No newline at end of file
+}
diff --git a/compos/apk/assets/vm_test_config.json b/compos/apk/assets/vm_test_config.json
index 9fd55b7..16d1037 100644
--- a/compos/apk/assets/vm_test_config.json
+++ b/compos/apk/assets/vm_test_config.json
@@ -1,21 +1,24 @@
 {
-    "version": 1,
-    "os": {
-        "name": "microdroid"
+  "version": 1,
+  "os": {
+    "name": "microdroid"
+  },
+  "task": {
+    "type": "executable",
+    "command": "/apex/com.android.compos/bin/compsvc"
+  },
+  "apexes": [
+    {
+      "name": "com.android.art"
     },
-    "task": {
-        "type": "executable",
-        "command": "/apex/com.android.compos/bin/compsvc"
+    {
+      "name": "com.android.compos"
     },
-    "apexes": [
-        {
-            "name": "com.android.art"
-        },
-        {
-            "name": "com.android.compos"
-        },
-        {
-            "name": "{CLASSPATH}"
-        }
-    ]
-}
\ No newline at end of file
+    {
+      "name": "com.android.sdkext"
+    },
+    {
+      "name": "{CLASSPATH}"
+    }
+  ]
+}
diff --git a/compos/composd/src/instance_starter.rs b/compos/composd/src/instance_starter.rs
index 729e5b6..6946c11 100644
--- a/compos/composd/src/instance_starter.rs
+++ b/compos/composd/src/instance_starter.rs
@@ -29,7 +29,6 @@
     COMPOS_DATA_ROOT, IDSIG_FILE, INSTANCE_IMAGE_FILE, PRIVATE_KEY_BLOB_FILE, PUBLIC_KEY_FILE,
 };
 use log::{info, warn};
-use std::env;
 use std::fs;
 use std::path::{Path, PathBuf};
 
@@ -111,8 +110,7 @@
         // If we get this far then the instance image is valid in the current context (e.g. the
         // current set of APEXes) and the key blob can be successfully decrypted by the VM. So the
         // files have not been tampered with and we're good to go.
-
-        Self::initialize_service(service, &key_blob)?;
+        service.initializeSigningKey(&key_blob).context("Loading signing key")?;
 
         Ok(compos_instance)
     }
@@ -145,28 +143,11 @@
 
         // Unlike when starting an existing instance, we don't need to verify the key, since we
         // just generated it and have it in memory.
-
-        Self::initialize_service(service, &key_data.keyBlob)?;
+        service.initializeSigningKey(&key_data.keyBlob).context("Loading signing key")?;
 
         Ok(compos_instance)
     }
 
-    fn initialize_service(service: &Strong<dyn ICompOsService>, key_blob: &[u8]) -> Result<()> {
-        // Key blob is assumed to be verified/trusted.
-        service.initializeSigningKey(key_blob).context("Loading signing key")?;
-
-        // TODO(198211396): Implement correctly.
-        service
-            .initializeClasspaths(
-                &env::var("BOOTCLASSPATH")?,
-                &env::var("DEX2OATBOOTCLASSPATH")?,
-                &env::var("SYSTEMSERVERCLASSPATH")?,
-                &env::var("STANDALONE_SYSTEMSERVER_JARS")?,
-            )
-            .context("Initializing *CLASSPATH")?;
-        Ok(())
-    }
-
     fn start_vm(
         &self,
         virtualization_service: &dyn IVirtualizationService,
diff --git a/compos/src/compilation.rs b/compos/src/compilation.rs
index 2ca4dd4..af7a9b4 100644
--- a/compos/src/compilation.rs
+++ b/compos/src/compilation.rs
@@ -15,12 +15,15 @@
  */
 
 use anyhow::{anyhow, bail, Context, Result};
-use log::{debug, error, info};
+use log::{debug, error, info, warn};
 use minijail::{self, Minijail};
+use regex::Regex;
 use std::env;
+use std::ffi::OsString;
 use std::fs::{read_dir, File};
 use std::os::unix::io::{AsRawFd, RawFd};
 use std::path::{self, Path, PathBuf};
+use std::process::Command;
 
 use crate::artifact_signer::ArtifactSigner;
 use crate::compos_key_service::Signer;
@@ -129,6 +132,8 @@
 
     let staging_dir = mountpoint.join(context.staging_dir_fd.to_string());
 
+    set_classpaths(&android_root)?;
+
     let args = vec![
         "odrefresh".to_string(),
         format!("--zygote-arch={}", context.zygote_arch),
@@ -164,6 +169,53 @@
     Ok(exit_code)
 }
 
+fn set_classpaths(android_root: &Path) -> Result<()> {
+    let export_lines = run_derive_classpath(android_root)?;
+    load_classpath_vars(&export_lines)
+}
+
+fn run_derive_classpath(android_root: &Path) -> Result<String> {
+    let classpaths_root = android_root.join("etc/classpaths");
+
+    let mut bootclasspath_arg = OsString::new();
+    bootclasspath_arg.push("--bootclasspath-fragment=");
+    bootclasspath_arg.push(classpaths_root.join("bootclasspath.pb"));
+
+    let mut systemserverclasspath_arg = OsString::new();
+    systemserverclasspath_arg.push("--systemserverclasspath-fragment=");
+    systemserverclasspath_arg.push(classpaths_root.join("systemserverclasspath.pb"));
+
+    let result = Command::new("/apex/com.android.sdkext/bin/derive_classpath")
+        .arg(bootclasspath_arg)
+        .arg(systemserverclasspath_arg)
+        .arg("/proc/self/fd/1")
+        .output()
+        .context("Failed to run derive_classpath")?;
+
+    if !result.status.success() {
+        bail!("derive_classpath returned {}", result.status);
+    }
+
+    String::from_utf8(result.stdout).context("Converting derive_classpath output")
+}
+
+fn load_classpath_vars(export_lines: &str) -> Result<()> {
+    // Each line should be in the format "export <var name> <value>"
+    let pattern = Regex::new(r"^export ([^ ]+) ([^ ]+)$").context("Failed to construct Regex")?;
+    for line in export_lines.lines() {
+        if let Some(captures) = pattern.captures(line) {
+            let name = &captures[1];
+            let value = &captures[2];
+            // TODO(b/213416778) Don't modify our env, construct a fresh one for odrefresh
+            env::set_var(name, value);
+        } else {
+            warn!("Malformed line from derive_classpath: {}", line);
+        }
+    }
+
+    Ok(())
+}
+
 fn add_artifacts(target_dir: &Path, artifact_signer: &mut ArtifactSigner) -> Result<()> {
     for entry in
         read_dir(&target_dir).with_context(|| format!("Traversing {}", target_dir.display()))?
diff --git a/compos/src/compsvc.rs b/compos/src/compsvc.rs
index 3e9fc34..ef3ae2a 100644
--- a/compos/src/compsvc.rs
+++ b/compos/src/compsvc.rs
@@ -23,7 +23,6 @@
 use compos_common::binder::to_binder_result;
 use log::warn;
 use std::default::Default;
-use std::env;
 use std::path::PathBuf;
 use std::sync::RwLock;
 
@@ -95,21 +94,6 @@
         }
     }
 
-    fn initializeClasspaths(
-        &self,
-        boot_classpath: &str,
-        dex2oat_boot_classpath: &str,
-        system_server_classpath: &str,
-        standalone_systemserver_jars: &str,
-    ) -> BinderResult<()> {
-        // TODO(198211396): Implement correctly.
-        env::set_var("BOOTCLASSPATH", boot_classpath);
-        env::set_var("DEX2OATBOOTCLASSPATH", dex2oat_boot_classpath);
-        env::set_var("SYSTEMSERVERCLASSPATH", system_server_classpath);
-        env::set_var("STANDALONE_SYSTEMSERVER_JARS", standalone_systemserver_jars);
-        Ok(())
-    }
-
     fn odrefresh(
         &self,
         system_dir_fd: i32,