diff --git a/runtime/java_vm_ext.cc b/runtime/java_vm_ext.cc
index 7cc05f7..58da7f2 100644
--- a/runtime/java_vm_ext.cc
+++ b/runtime/java_vm_ext.cc
@@ -736,7 +736,7 @@
     // it's okay to decode it without worrying about unexpectedly marking it alive.
     mirror::ClassLoader* loader = soa.Decode<mirror::ClassLoader*>(class_loader);
     class_loader_allocator =
-        Runtime::Current()->GetClassLinker()->GetAllocatorForClassLoader(loader);
+        Runtime::Current()->GetClassLinker()->GetOrCreateAllocatorForClassLoader(loader);
     CHECK(class_loader_allocator != nullptr);
   }
   if (library != nullptr) {
diff --git a/test/068-classloader/expected.txt b/test/068-classloader/expected.txt
index 8725799..36e4f48 100644
--- a/test/068-classloader/expected.txt
+++ b/test/068-classloader/expected.txt
@@ -13,3 +13,4 @@
 Got LinkageError on IDI (early)
 class Main
 Got expected ClassNotFoundException
+JNI_OnLoad called
diff --git a/test/068-classloader/src/FancyLoader.java b/test/068-classloader/src/FancyLoader.java
index 6a153cc..b8eac7b 100644
--- a/test/068-classloader/src/FancyLoader.java
+++ b/test/068-classloader/src/FancyLoader.java
@@ -38,7 +38,7 @@
     static final String CLASS_PATH = "classes-ex/";
 
     /* this is the "alternate" DEX/Jar file */
-    static final String DEX_FILE = System.getenv("DEX_LOCATION") + "/068-classloader-ex.jar";
+    public static final String DEX_FILE = System.getenv("DEX_LOCATION") + "/068-classloader-ex.jar";
 
     /* on Dalvik, this is a DexFile; otherwise, it's null */
     private Class mDexClass;
diff --git a/test/068-classloader/src/Main.java b/test/068-classloader/src/Main.java
index 361e293..e3bf82c 100644
--- a/test/068-classloader/src/Main.java
+++ b/test/068-classloader/src/Main.java
@@ -14,6 +14,8 @@
  * limitations under the License.
  */
 
+import java.lang.reflect.Constructor;
+import java.lang.reflect.Method;
 /**
  * Class loader test.
  */
@@ -62,6 +64,28 @@
         testSeparation();
 
         testClassForName();
+
+        // Attempt to load without a class table, regression test for b/25866849.
+        testLoadNativeLibrary(args[0]);
+    }
+
+    static void testLoadNativeLibrary(String libName) throws Exception {
+        Class pathClassLoader = Class.forName("dalvik.system.PathClassLoader");
+        if (pathClassLoader == null) {
+            throw new AssertionError("Couldn't find path class loader class");
+        }
+        Constructor constructor =
+            pathClassLoader.getDeclaredConstructor(String.class, ClassLoader.class);
+        ClassLoader loader = (ClassLoader) constructor.newInstance(
+            FancyLoader.DEX_FILE, ClassLoader.getSystemClassLoader());
+        Runtime runtime = Runtime.getRuntime();
+        Method method = runtime.getClass().getDeclaredMethod("loadLibrary", String.class,
+            ClassLoader.class);
+        if (method == null) {
+            throw new RuntimeException("loadLibrary not found");
+        }
+        method.setAccessible(true);
+        method.invoke(runtime, libName, loader);
     }
 
     static void testSeparation() {