diff --git a/dev/core/src/com/google/gwt/dev/jjs/ast/RuntimeConstants.java b/dev/core/src/com/google/gwt/dev/jjs/ast/RuntimeConstants.java
index 5fc3c2b..15f5b8e 100644
--- a/dev/core/src/com/google/gwt/dev/jjs/ast/RuntimeConstants.java
+++ b/dev/core/src/com/google/gwt/dev/jjs/ast/RuntimeConstants.java
@@ -92,6 +92,7 @@
   public static final String RUNTIME_GET_CLASS_PROTOTYPE = "Runtime.getClassPrototype";
   public static final String RUNTIME_MAKE_LAMBDA_FUNCTION = "Runtime.makeLambdaFunction";
   public static final String RUNTIME_PROVIDE = "Runtime.provide";
+  public static final String RUNTIME_TO_STRING = "Runtime.toString";
   public static final String RUNTIME_TYPE_MARKER_FN = "Runtime.typeMarkerFn";
   public static final String RUNTIME_UNIQUE_ID = "Runtime.uniqueId";
 
diff --git a/dev/core/src/com/google/gwt/dev/jjs/impl/Devirtualizer.java b/dev/core/src/com/google/gwt/dev/jjs/impl/Devirtualizer.java
index 5bd2725..d0ffe59 100644
--- a/dev/core/src/com/google/gwt/dev/jjs/impl/Devirtualizer.java
+++ b/dev/core/src/com/google/gwt/dev/jjs/impl/Devirtualizer.java
@@ -245,8 +245,12 @@
       // and optimizations need to be strong enough to perform the same kind of size reductions
       // achieved by keeping track of singleImpls.
 
-      //
-      if (!program.typeOracle.isDualJsoInterface(targetType) &&
+      if (method.getSignature().equals("toString()Ljava/lang/String;")) {
+        // Object.toString is special because: 1) every JS object has it and 2) GWT creates
+        // a bridge from toString to its implementation method.
+        devirtualMethodByMethod.put(
+            method, program.getIndexedMethod(RuntimeConstants.RUNTIME_TO_STRING));
+      } else if (!program.typeOracle.isDualJsoInterface(targetType) &&
           program.typeOracle.isSingleJsoImpl(targetType)) {
         // Optimize the trampoline away when there is ONLY JSO dispatch.
         // TODO(rluble): verify that this case can not arise in optimized mode and if so
diff --git a/dev/core/src/com/google/gwt/dev/jjs/impl/MethodCallTightener.java b/dev/core/src/com/google/gwt/dev/jjs/impl/MethodCallTightener.java
index ec80e56..5ccf347 100644
--- a/dev/core/src/com/google/gwt/dev/jjs/impl/MethodCallTightener.java
+++ b/dev/core/src/com/google/gwt/dev/jjs/impl/MethodCallTightener.java
@@ -72,33 +72,57 @@
         return;
       }
 
-      JMethodCall newCall = maybeUpgradeToNonPolymorphicCall(x);
-
-      // If the call is still polymorphic, try tightening the method.
-      if (newCall.canBePolymorphic()) {
-        newCall = maybeTightenMethodCall(newCall);
+      JMethod mostSpecificTarget = getMostSpecificOverride(x);
+      if (mostSpecificTarget.getEnclosingType().isJsNative()) {
+        // Never tighten to instance methods in native types. This done because java.lang.Object
+        // methods are implicitly implemented by all objects but may or may not be present in the
+        // native type implementation. The dispatch for these is eventually done through a
+        // trampoline {@see Devirtualizer} that makes the proper checks and invokes the native
+        // implementation if present.
+        assert x.getTarget().getEnclosingType().isJavaLangObject()
+            || x.getTarget().getEnclosingType().isJsNative();
+        return;
       }
 
+      // Tighten the method call if a more specific override is available.
+      JMethodCall newCall = maybeReplaceTargetMethod(x, mostSpecificTarget);
+      maybeUpgradeToNonPolymorphicCall(newCall);
+
       if (newCall != x) {
         ctx.replaceMe(newCall);
       }
     }
 
-    private JMethodCall maybeUpgradeToNonPolymorphicCall(JMethodCall x) {
+    private JMethod getMostSpecificOverride(final JMethodCall methodCall) {
+      JMethod original = methodCall.getTarget();
+      JClassType underlyingType =
+          (JClassType) methodCall.getInstance().getType().getUnderlyingType();
+
+      return program.typeOracle.findMostSpecificOverride(underlyingType, original);
+    }
+
+    private JMethodCall maybeReplaceTargetMethod(JMethodCall methodCall, JMethod newTargetMethod) {
+      if (methodCall.getTarget() == newTargetMethod) {
+        return methodCall;
+      }
+      return new JMethodCall(
+          methodCall.getSourceInfo(),
+          methodCall.getInstance(),
+          newTargetMethod,
+          methodCall.getArgs());
+    }
+
+    private void maybeUpgradeToNonPolymorphicCall(JMethodCall x) {
       JReferenceType instanceType = (JReferenceType) x.getInstance().getType();
 
-      if (!instanceType.canBeSubclass()) {
-        // Mark a call as non-polymorphic if the targeted type is guaranteed to be not a subclass.
-        x = maybeTightenMethodCall(x);
-        x.setCannotBePolymorphic();
-        madeChanges();
-      } else if (!hasPotentialOverride(instanceType, x.getTarget())) {
-        // Mark a call as non-polymorphic if the targeted method is the only possible dispatch.
+      if (!instanceType.canBeSubclass() || !hasPotentialOverride(instanceType, x.getTarget())) {
+        assert getMostSpecificOverride(x) == x.getTarget();
+
+        // Mark a call as non-polymorphic if the targeted type is guaranteed to be not a subclass
+        // or there are no overriding implementations.
         x.setCannotBePolymorphic();
         madeChanges();
        }
-
-      return x;
     }
 
     private boolean hasPotentialOverride(JReferenceType instanceType, JMethod target) {
@@ -117,27 +141,6 @@
       return false;
     }
 
-    private JMethodCall maybeTightenMethodCall(final JMethodCall methodCall) {
-      JMethod original = methodCall.getTarget();
-      JClassType underlyingType =
-          (JClassType) methodCall.getInstance().getType().getUnderlyingType();
-
-      JMethod mostSpecificOverride =
-          program.typeOracle.findMostSpecificOverride(underlyingType, original);
-
-      if (mostSpecificOverride == original
-          // Never tighten object methods to native implementations. This decision forces
-          // the use of the Object trampoline for hashcCode, equals and toString.
-          || (original.getEnclosingType().isJavaLangObject()
-              && mostSpecificOverride.isJsNative())) {
-        return methodCall;
-      }
-      JMethodCall newCall = new JMethodCall(
-          methodCall.getSourceInfo(), methodCall.getInstance(), mostSpecificOverride);
-      newCall.addArgs(methodCall.getArgs());
-      return newCall;
-    }
-
     @Override
     public void endVisit(JNewInstance x, Context ctx) {
       // Do not tighten new operations.
diff --git a/dev/core/super/com/google/gwt/dev/jjs/intrinsic/com/google/gwt/lang/Runtime.java b/dev/core/super/com/google/gwt/dev/jjs/intrinsic/com/google/gwt/lang/Runtime.java
index e48652b..c7c7606 100644
--- a/dev/core/super/com/google/gwt/dev/jjs/intrinsic/com/google/gwt/lang/Runtime.java
+++ b/dev/core/super/com/google/gwt/dev/jjs/intrinsic/com/google/gwt/lang/Runtime.java
@@ -212,4 +212,11 @@
     }
     Object.defineProperties(proto,  propertyDefinition);
   }-*/;
+
+  public static native String toString(Object object) /*-{
+    if (Array.isArray(object) && @Util::hasTypeMarker(*)(object)) {
+       return @Object::toString(Ljava/lang/Object;)(object);
+    }
+    return object.toString();
+  }-*/;
 }
diff --git a/dev/core/test/com/google/gwt/dev/javac/typemodel/JParameterizedTypeTest.java b/dev/core/test/com/google/gwt/dev/javac/typemodel/JParameterizedTypeTest.java
index 1180055..34cba2a 100644
--- a/dev/core/test/com/google/gwt/dev/javac/typemodel/JParameterizedTypeTest.java
+++ b/dev/core/test/com/google/gwt/dev/javac/typemodel/JParameterizedTypeTest.java
@@ -433,7 +433,8 @@
     expectedMethods.addAll(expected);
     if (addObjectMethods) {
       TypeOracle oracle = moduleContext.getOracle();
-      expectedMethods.addAll(Arrays.asList(oracle.getJavaLangObject().getMethods()));
+      expectedMethods.addAll(
+          Arrays.asList(oracle.getJavaLangObject().getOverridableMethods()));
     }
 
     for (JMethod method : actual) {
diff --git a/dev/core/test/com/google/gwt/dev/jjs/JavaAstConstructor.java b/dev/core/test/com/google/gwt/dev/jjs/JavaAstConstructor.java
index 3bf511a..7e5f7bc 100644
--- a/dev/core/test/com/google/gwt/dev/jjs/JavaAstConstructor.java
+++ b/dev/core/test/com/google/gwt/dev/jjs/JavaAstConstructor.java
@@ -292,6 +292,7 @@
                   "  public static void bootstrap() {}",
                   "  public static void emptyMethod() {}",
                   "  public static void getClassPrototype() {}",
+                  "  public static String toString(Object object) { return null; }",
                   "  static native void typeMarkerFn() /*-{}-*/;",
                   "}");
         }
diff --git a/dev/core/test/com/google/gwt/dev/jjs/impl/DevirtualizerTest.java b/dev/core/test/com/google/gwt/dev/jjs/impl/DevirtualizerTest.java
index ccc1c71..88bd4f5 100644
--- a/dev/core/test/com/google/gwt/dev/jjs/impl/DevirtualizerTest.java
+++ b/dev/core/test/com/google/gwt/dev/jjs/impl/DevirtualizerTest.java
@@ -151,8 +151,78 @@
     result.intoString(expected);
   }
 
+  public void testDevirtualizeObjectMethods() throws UnableToCompleteException {
+    addSnippetImport("jsinterop.annotations.JsType");
+    addSnippetImport("jsinterop.annotations.JsOverlay");
+    addSnippetClassDecl(
+        "@JsType(isNative=true) public static class NativeClass {",
+        "}",
+        "public static class NativeClassSubclass extends NativeClass {",
+        "}");
+
+    String code = Joiner.on('\n').join(
+        "NativeClass nativeClass = null;",
+        "nativeClass.toString();",
+        "nativeClass.equals(nativeClass);",
+        "nativeClass.hashCode();",
+        "NativeClassSubclass subclass = null;",
+        "subclass.toString();",
+        "subclass.equals(subclass);",
+        "subclass.hashCode();"
+        );
+
+    String expected = Joiner.on('\n').join(
+        "EntryPoint$NativeClass nativeClass = null;",
+        "Runtime.toString(nativeClass);",
+        "Object.equals_Ljava_lang_Object__Z__devirtual$(nativeClass, nativeClass);",
+        "Object.hashCode__I__devirtual$(nativeClass);",
+        "EntryPoint$NativeClassSubclass subclass = null;",
+        "Runtime.toString(subclass);",
+        "Object.equals_Ljava_lang_Object__Z__devirtual$(subclass, subclass);",
+        "Object.hashCode__I__devirtual$(subclass);");
+    Result result = optimize("void", code);
+    result.intoString(expected);
+  }
+
+  public void testDevirtualizeObjectMethodsExplicitelyDefined() throws UnableToCompleteException {
+    addSnippetImport("jsinterop.annotations.JsType");
+    addSnippetImport("jsinterop.annotations.JsOverlay");
+    addSnippetClassDecl(
+        "@JsType(isNative=true) public static class NativeClass {",
+        "  public native String toString();",
+        "  public native int hashCode();",
+        "  public native boolean equals(Object o);",
+        "}",
+        "public static class NativeClassSubclass extends NativeClass {",
+        "}");
+
+    String code = Joiner.on('\n').join(
+        "NativeClass nativeClass = null;",
+        "nativeClass.toString();",
+        "nativeClass.equals(nativeClass);",
+        "nativeClass.hashCode();",
+        "NativeClassSubclass subclass = null;",
+        "subclass.toString();",
+        "subclass.equals(subclass);",
+        "subclass.hashCode();"
+    );
+
+    String expected = Joiner.on('\n').join(
+        "EntryPoint$NativeClass nativeClass = null;",
+        "Runtime.toString(nativeClass);",
+        "Object.equals_Ljava_lang_Object__Z__devirtual$(nativeClass, nativeClass);",
+        "Object.hashCode__I__devirtual$(nativeClass);",
+        "EntryPoint$NativeClassSubclass subclass = null;",
+        "Runtime.toString(subclass);",
+        "Object.equals_Ljava_lang_Object__Z__devirtual$(subclass, subclass);",
+        "Object.hashCode__I__devirtual$(subclass);");
+    Result result = optimize("void", code);
+    result.intoString(expected);
+  }
+
   @Override
   protected boolean doOptimizeMethod(TreeLogger logger, JProgram program, JMethod method) {
+    ReplaceCallsToNativeJavaLangObjectOverrides.exec(program);
     Devirtualizer.exec(program);
     return true;
   }
diff --git a/user/super/com/google/gwt/emul/java/lang/Object.java b/user/super/com/google/gwt/emul/java/lang/Object.java
index 523beba..3dc8582 100644
--- a/user/super/com/google/gwt/emul/java/lang/Object.java
+++ b/user/super/com/google/gwt/emul/java/lang/Object.java
@@ -77,9 +77,12 @@
   }
 
   public String toString() {
-    return getClass().getName() + '@' + Integer.toHexString(hashCode());
+    return toString(this);
   }
 
+  private static String toString(Object object) {
+    return object.getClass().getName() + '@' + Integer.toHexString(object.hashCode());
+  }
   /**
    * Never called; here for JRE compatibility.
    *
diff --git a/user/test/com/google/gwt/core/interop/NativeJsTypeTest.java b/user/test/com/google/gwt/core/interop/NativeJsTypeTest.java
index b222732..4cf5378 100644
--- a/user/test/com/google/gwt/core/interop/NativeJsTypeTest.java
+++ b/user/test/com/google/gwt/core/interop/NativeJsTypeTest.java
@@ -471,9 +471,15 @@
 
   @JsType(isNative = true, namespace = JsPackage.GLOBAL, name = "Error")
   private static class NativeError {
+    public String message;
   }
 
+  private static final String ERROR_FROM_NATIVE_ERROR_SUBCLASS = "error from NativeErrorSubclass";
+
   private static class NativeErrorSubclass extends NativeError {
+    public NativeErrorSubclass() {
+      message = ERROR_FROM_NATIVE_ERROR_SUBCLASS;
+    }
   }
 
   public void testObjectPropertiesAreCopied() {
@@ -482,8 +488,6 @@
     // Make sure the subclass is a proper Java object (the typeMarker should be one of the
     // properties copied from java.lang.Object).
     assertFalse(error instanceof JavaScriptObject);
-    // TODO(rluble): NativeErrorSubclass should have inherited Error toString behavior not
-    // j.l.Object.toString behavior.
-    // assertTrue(error.toString().matches("[0-9a-zA-Z$_.]+@[0-9a-fA-F]+"));
+    assertTrue(error.toString().contains(ERROR_FROM_NATIVE_ERROR_SUBCLASS));
   }
 }