diff --git a/tests/BinaryTransparencyHostTest/Android.bp b/tests/BinaryTransparencyHostTest/Android.bp
index 142e3dd..dc6bdff 100644
--- a/tests/BinaryTransparencyHostTest/Android.bp
+++ b/tests/BinaryTransparencyHostTest/Android.bp
@@ -35,6 +35,7 @@
     data: [
         ":BinaryTransparencyTestApp",
         ":EasterEgg",
+        ":com.android.apex.cts.shim.v2_rebootless_prebuilt",
     ],
     test_suites: [
         "general-tests",
diff --git a/tests/BinaryTransparencyHostTest/src/android/transparency/test/BinaryTransparencyHostTest.java b/tests/BinaryTransparencyHostTest/src/android/transparency/test/BinaryTransparencyHostTest.java
index 84bed92..8db3d00 100644
--- a/tests/BinaryTransparencyHostTest/src/android/transparency/test/BinaryTransparencyHostTest.java
+++ b/tests/BinaryTransparencyHostTest/src/android/transparency/test/BinaryTransparencyHostTest.java
@@ -17,6 +17,7 @@
 package android.transparency.test;
 
 import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
 
 import com.android.tradefed.device.DeviceNotAvailableException;
 import com.android.tradefed.testtype.DeviceJUnit4ClassRunner;
@@ -29,14 +30,22 @@
 import org.junit.Test;
 import org.junit.runner.RunWith;
 
+import java.util.concurrent.TimeUnit;
+
 // TODO: Add @Presubmit
 @RunWith(DeviceJUnit4ClassRunner.class)
 public final class BinaryTransparencyHostTest extends BaseHostJUnit4Test {
     private static final String PACKAGE_NAME = "android.transparency.test.app";
 
+    private static final String JOB_ID = "1740526926";
+
+    /** Waiting time for the job to be scheduled */
+    private static final int JOB_CREATION_MAX_SECONDS = 5;
+
     @After
     public void tearDown() throws Exception {
         uninstallPackage("com.android.egg");
+        uninstallRebootlessApex();
     }
 
     @Test
@@ -64,6 +73,28 @@
     }
 
     @Test
+    public void testRebootlessApexUpdateTriggersJobScheduling() throws Exception {
+        cancelPendingJob();
+        installRebootlessApex();
+
+        // Verify
+        expectJobToBeScheduled();
+        // Just cancel since we can't verifying very meaningfully.
+        cancelPendingJob();
+    }
+
+    @Test
+    public void testPreloadUpdateTriggersJobScheduling() throws Exception {
+        cancelPendingJob();
+        installPackage("EasterEgg.apk");
+
+        // Verify
+        expectJobToBeScheduled();
+        // Just cancel since we can't verifying very meaningfully.
+        cancelPendingJob();
+    }
+
+    @Test
     public void testMeasureMbas() throws Exception {
         // TODO(265244016): figure out a way to install an MBA
     }
@@ -74,4 +105,47 @@
         options.setTestMethodName(method);
         runDeviceTests(options);
     }
+
+    private void cancelPendingJob() throws DeviceNotAvailableException {
+        CommandResult result = getDevice().executeShellV2Command(
+                "cmd jobscheduler cancel android " + JOB_ID);
+        assertTrue(result.getStatus() == CommandStatus.SUCCESS);
+    }
+
+    private void expectJobToBeScheduled() throws Exception {
+        for (int i = 0; i < JOB_CREATION_MAX_SECONDS; i++) {
+            CommandResult result = getDevice().executeShellV2Command(
+                    "cmd jobscheduler get-job-state android " + JOB_ID);
+            String state = result.getStdout().toString();
+            if (state.startsWith("unknown")) {
+                // The job hasn't been scheduled yet. So try again.
+                TimeUnit.SECONDS.sleep(1);
+            } else if (result.getExitCode() != 0) {
+                fail("Failing due to unexpected job state: " + result);
+            } else {
+                // The job exists, which is all we care about here
+                return;
+            }
+        }
+        fail("Timed out waiting for the job to be scheduled");
+    }
+
+    private void installRebootlessApex() throws Exception {
+        installPackage("com.android.apex.cts.shim.v2_rebootless.apex", "--force-non-staged");
+    }
+
+    private void uninstallRebootlessApex() throws DeviceNotAvailableException {
+        // Reboot only if the APEX is not the pre-install one.
+        CommandResult result = getDevice().executeShellV2Command(
+                "pm list packages -f --apex-only |grep com.android.apex.cts.shim");
+        assertTrue(result.getStatus() == CommandStatus.SUCCESS);
+        if (result.getStdout().contains("/data/apex/active/")) {
+            uninstallPackage("com.android.apex.cts.shim");
+            getDevice().reboot();
+
+            // Reboot enforces SELinux. Make it permissive again.
+            CommandResult runResult = getDevice().executeShellV2Command("setenforce 0");
+            assertTrue(runResult.getStatus() == CommandStatus.SUCCESS);
+        }
+    }
 }