diff --git a/runtime/jni_internal.cc b/runtime/jni_internal.cc
index fd386d7..ca45f76 100644
--- a/runtime/jni_internal.cc
+++ b/runtime/jni_internal.cc
@@ -311,6 +311,30 @@
     return; \
   }
 
+template <bool kNative>
+static mirror::ArtMethod* FindMethod(mirror::Class* c,
+                                     const StringPiece& name,
+                                     const StringPiece& sig)
+    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  for (size_t i = 0; i < c->NumDirectMethods(); ++i) {
+    mirror::ArtMethod* method = c->GetDirectMethod(i);
+    if (kNative == method->IsNative() &&
+        name == method->GetName() && method->GetSignature() == sig) {
+      return method;
+    }
+  }
+
+  for (size_t i = 0; i < c->NumVirtualMethods(); ++i) {
+    mirror::ArtMethod* method = c->GetVirtualMethod(i);
+    if (kNative == method->IsNative() &&
+        name == method->GetName() && method->GetSignature() == sig) {
+      return method;
+    }
+  }
+
+  return nullptr;
+}
+
 class JNI {
  public:
   static jint GetVersion(JNIEnv*) {
@@ -2133,10 +2157,33 @@
         ++sig;
       }
 
-      mirror::ArtMethod* m = c->FindDirectMethod(name, sig);
-      if (m == nullptr) {
-        m = c->FindVirtualMethod(name, sig);
+      // Note: the right order is to try to find the method locally
+      // first, either as a direct or a virtual method. Then move to
+      // the parent.
+      mirror::ArtMethod* m = nullptr;
+      bool warn_on_going_to_parent = down_cast<JNIEnvExt*>(env)->vm->IsCheckJniEnabled();
+      for (mirror::Class* current_class = c;
+           current_class != nullptr;
+           current_class = current_class->GetSuperClass()) {
+        // Search first only comparing methods which are native.
+        m = FindMethod<true>(current_class, name, sig);
+        if (m != nullptr) {
+          break;
+        }
+
+        // Search again comparing to all methods, to find non-native methods that match.
+        m = FindMethod<false>(current_class, name, sig);
+        if (m != nullptr) {
+          break;
+        }
+
+        if (warn_on_going_to_parent) {
+          LOG(WARNING) << "CheckJNI: method to register \"" << name << "\" not in the given class. "
+                       << "This is slow, consider changing your RegisterNatives calls.";
+          warn_on_going_to_parent = false;
+        }
       }
+
       if (m == nullptr) {
         LOG(return_errors ? ERROR : INTERNAL_FATAL) << "Failed to register native method "
             << PrettyDescriptor(c) << "." << name << sig << " in "
diff --git a/test/139-register-natives/check b/test/139-register-natives/check
new file mode 100755
index 0000000..265ad85
--- /dev/null
+++ b/test/139-register-natives/check
@@ -0,0 +1,20 @@
+#!/bin/bash
+#
+# Copyright (C) 2015 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.
+
+# Strip any JNI registration error messages
+sed -e '/java_vm_ext/d' -e '/jni_internal.cc/d' "$2" > "$2.tmp"
+
+diff --strip-trailing-cr -q "$1" "$2.tmp" >/dev/null
diff --git a/test/139-register-natives/expected.txt b/test/139-register-natives/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/139-register-natives/expected.txt
diff --git a/test/139-register-natives/info.txt b/test/139-register-natives/info.txt
new file mode 100644
index 0000000..48e08a4
--- /dev/null
+++ b/test/139-register-natives/info.txt
@@ -0,0 +1 @@
+Tests the correct order of RegisterNatives.
diff --git a/test/139-register-natives/regnative.cc b/test/139-register-natives/regnative.cc
new file mode 100644
index 0000000..d9c8b31
--- /dev/null
+++ b/test/139-register-natives/regnative.cc
@@ -0,0 +1,33 @@
+/*
+ * Copyright (C) 2015 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.
+ */
+
+#include "jni.h"
+
+namespace art {
+
+// Simple empty method. We will check for correct registration with UnsatisfiedLinkError.
+static void foo(JNIEnv*, jclass) {
+}
+
+static JNINativeMethod gMethods[] = {
+    { "foo", "()V", reinterpret_cast<void*>(foo) }
+};
+
+extern "C" JNIEXPORT jint JNICALL Java_Main_registerNatives(JNIEnv* env, jclass, jclass trg) {
+  return env->RegisterNatives(trg, gMethods, 1);
+}
+
+}  // namespace art
diff --git a/test/139-register-natives/src/Main.java b/test/139-register-natives/src/Main.java
new file mode 100644
index 0000000..35b2f9c
--- /dev/null
+++ b/test/139-register-natives/src/Main.java
@@ -0,0 +1,120 @@
+/*
+ * Copyright (C) 2015 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.
+ */
+
+public class Main {
+  public static void main(String[] args) {
+    testRegistration1();
+    testRegistration2();
+    testRegistration3();
+  }
+
+  static {
+    System.loadLibrary("arttest");
+  }
+
+  // Test that a subclass' method is registered instead of a superclass' method.
+  private static void testRegistration1() {
+    registerNatives(TestSub.class);
+
+    expectNotThrows(new TestSub());
+    expectThrows(new TestSuper());
+  }
+
+  // Test that a superclass' method is registered if the subclass doesn't have a matching method.
+  private static void testRegistration2() {
+    registerNatives(TestSub2.class);
+
+    expectNotThrows(new TestSub2());
+    expectNotThrows(new TestSuper2());
+  }
+
+  // Test that registration fails if the subclass has a matching non-native method.
+  private static void testRegistration3() {
+    try {
+      registerNatives(TestSub3.class);
+      System.out.println("Expected exception for registerNatives(TestSub3.class)");
+    } catch (NoSuchMethodError ignored) {
+    }
+  }
+
+  private native static int registerNatives(Class c);
+
+  private static void expectThrows(Base b) {
+    try {
+      b.callMyFoo();
+      System.out.println("Expected exception for " + b.getClass().getName());
+    } catch (Throwable ignored) {
+    }
+  }
+
+  private static void expectNotThrows(Base b) {
+    try {
+      b.callMyFoo();
+    } catch (Throwable t) {
+      System.out.println("Did not expect an exception for " + b.getClass().getName());
+      t.printStackTrace(System.out);
+    }
+  }
+}
+
+abstract class Base {
+  public abstract void callMyFoo();
+}
+
+class TestSuper extends Base {
+  private native void foo();
+
+  @Override
+  public void callMyFoo() {
+    foo();
+  }
+}
+
+class TestSub extends TestSuper {
+  public native void foo();
+
+  @Override
+  public void callMyFoo() {
+    foo();
+  }
+}
+
+class TestSuper2 extends Base{
+  public native void foo();
+
+  @Override
+  public void callMyFoo() {
+    foo();
+  }
+}
+
+class TestSub2 extends TestSuper2 {
+}
+
+class TestSuper3 extends Base {
+  public native void foo();
+
+  @Override
+  public void callMyFoo() {
+    foo();
+  }
+}
+
+class TestSub3 extends TestSuper3 {
+  public void foo() {
+    System.out.println("TestSub3.foo()");
+  }
+}
diff --git a/test/Android.libarttest.mk b/test/Android.libarttest.mk
index 5e768ee..6ad8787 100644
--- a/test/Android.libarttest.mk
+++ b/test/Android.libarttest.mk
@@ -28,6 +28,7 @@
   116-nodex2oat/nodex2oat.cc \
   117-nopatchoat/nopatchoat.cc \
   118-noimage-dex2oat/noimage-dex2oat.cc \
+  139-register-natives/regnative.cc \
   454-get-vreg/get_vreg_jni.cc \
   455-set-vreg/set_vreg_jni.cc \
   457-regs/regs_jni.cc \
diff --git a/test/Android.run-test.mk b/test/Android.run-test.mk
index 40f5f00..f6c9231 100644
--- a/test/Android.run-test.mk
+++ b/test/Android.run-test.mk
@@ -323,6 +323,7 @@
   118-noimage-dex2oat \
   119-noimage-patchoat \
   131-structural-change \
+  139-register-natives \
   454-get-vreg \
   455-set-vreg \
   457-regs \
diff --git a/test/etc/run-test-jar b/test/etc/run-test-jar
index 1c44958..240ed41 100755
--- a/test/etc/run-test-jar
+++ b/test/etc/run-test-jar
@@ -226,7 +226,11 @@
 
 if [ "$USE_JVM" = "y" ]; then
   # Xmx is necessary since we don't pass down the ART flags to JVM.
-  ${JAVA} ${DEBUGGER_OPTS} ${JVM_VERIFY_ARG} -Xmx256m -classpath classes $MAIN "$@"
+  cmdline="${JAVA} ${DEBUGGER_OPTS} ${JVM_VERIFY_ARG} -Xmx256m -classpath classes ${FLAGS} $MAIN $@"
+  if [ "$DEV_MODE" = "y" ]; then
+    echo $cmdline
+  fi
+  $cmdline
   exit
 fi
 
diff --git a/test/run-test b/test/run-test
index 2873a35..dc60eda 100755
--- a/test/run-test
+++ b/test/run-test
@@ -368,6 +368,9 @@
     else
       run_args="${run_args} --no-relocate"
     fi
+elif [ "$runtime" = "jvm" ]; then
+    # TODO: Detect whether the host is 32-bit or 64-bit.
+    run_args="${run_args} --runtime-option -Djava.library.path=${ANDROID_HOST_OUT}/lib64"
 fi
 
 if [ "$have_image" = "no" ]; then