diff --git a/src/main/java/com/android/tools/r8/optimize/MemberRebindingHelper.java b/src/main/java/com/android/tools/r8/optimize/MemberRebindingHelper.java
index 60b1176..14f21b3e 100644
--- a/src/main/java/com/android/tools/r8/optimize/MemberRebindingHelper.java
+++ b/src/main/java/com/android/tools/r8/optimize/MemberRebindingHelper.java
@@ -13,12 +13,14 @@
 import com.android.tools.r8.graph.DexDefinitionSupplier;
 import com.android.tools.r8.graph.DexEncodedMember;
 import com.android.tools.r8.graph.DexField;
+import com.android.tools.r8.graph.DexLibraryClass;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.LibraryMethod;
 import com.android.tools.r8.graph.MethodResolutionResult.SingleResolutionResult;
 import com.android.tools.r8.ir.code.InvokeType;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.utils.AndroidApiLevelUtils;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.collections.ProgramMethodSet;
 import com.google.common.collect.Iterables;
@@ -47,8 +49,10 @@
     if (invokeType.isDirect()) {
       return original;
     }
-
-    if (invokeType.isSuper() && options.canHaveSuperInvokeBug()) {
+    if ((invokeType.isSuper() && options.canHaveSuperInvokeBug())
+        || (invokeType.isVirtual()
+            && options.canHaveDalvikVerifyErrorOnVirtualInvokeWithMissingClasses()
+            && canBreakDalvikWithRebinding(resolutionResult))) {
       // To preserve semantics we should find the first library method on the boundary.
       DexType firstLibraryTarget =
           firstLibraryClassOrFirstInterfaceTarget(
@@ -113,6 +117,36 @@
     return newHolder != null ? original.withHolder(newHolder, appView.dexItemFactory()) : original;
   }
 
+  // On dalvik we can have hard verification errors if we rebind to known library classes that
+  // are super classes unknown library classes.
+  private boolean canBreakDalvikWithRebinding(SingleResolutionResult<?> resolutionResult) {
+    assert !resolutionResult.getResolvedHolder().isProgramClass();
+
+    DexClass current = resolutionResult.getInitialResolutionHolder();
+    while (current != null && !current.isLibraryClass()) {
+      current = appView.definitionFor(current.getSuperType());
+    }
+    if (current == null) {
+      assert resolutionResult.getResolvedHolder().isInterface();
+      return false;
+    }
+
+    DexLibraryClass currentLibraryClass = current.asLibraryClass();
+    while (currentLibraryClass != null) {
+      if (!AndroidApiLevelUtils.isApiSafeForReference(currentLibraryClass, appView)) {
+        return true;
+      }
+      if (!currentLibraryClass.hasSuperType()) {
+        // Object
+        break;
+      }
+      currentLibraryClass =
+          DexLibraryClass.asLibraryClassOrNull(
+              appView.definitionFor(currentLibraryClass.getSuperType()));
+    }
+    return false;
+  }
+
   private boolean canRebindDirectlyToLibraryMethod(
       DexClassAndMethod resolvedMethod,
       SingleResolutionResult<?> resolutionResult,
diff --git a/src/main/java/com/android/tools/r8/utils/InternalOptions.java b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
index 074df65..8cee41d 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -3288,4 +3288,11 @@
   public boolean canInitNewInstanceUsingSuperclassConstructor() {
     return isGeneratingDex() && minApiLevel.isGreaterThanOrEqualTo(AndroidApiLevel.L);
   }
+
+  // b/302826300 Dalvik can vms gives hard verification errors when we rebind program types to
+  // library types that are superclasses of unavailable classes on the specific api level.
+  // Instead, we should always rebind to just the first library class.
+  public boolean canHaveDalvikVerifyErrorOnVirtualInvokeWithMissingClasses() {
+    return canHaveBugPresentUntilExclusive(AndroidApiLevel.L);
+  }
 }
diff --git a/src/test/java/com/android/tools/r8/memberrebinding/LibraryMemberRebindingInterfaceTest.java b/src/test/java/com/android/tools/r8/memberrebinding/LibraryMemberRebindingInterfaceTest.java
index 90d4305..53740e7 100644
--- a/src/test/java/com/android/tools/r8/memberrebinding/LibraryMemberRebindingInterfaceTest.java
+++ b/src/test/java/com/android/tools/r8/memberrebinding/LibraryMemberRebindingInterfaceTest.java
@@ -136,6 +136,11 @@
       // If we are compiling to an old runtime with a new android.jar, we should rebind to LibraryB.
       return LibraryB.class;
     }
+    // On pre L we don't rebind above classes that we can't find in the api database
+    if (!parameters.isDexRuntime() || parameters.getApiLevel().isLessThan(AndroidApiLevel.L)) {
+      return LibraryB.class;
+    }
+
     // Otherwise, we are compiling to an old android.jar, in which case we should rebind to
     // LibraryI.
     return LibraryI.class;
diff --git a/src/test/java/com/android/tools/r8/memberrebinding/MemberRebindingWithApiDatabaseLookupTest.java b/src/test/java/com/android/tools/r8/memberrebinding/MemberRebindingWithApiDatabaseLookupTest.java
new file mode 100644
index 0000000..c9bec48
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/memberrebinding/MemberRebindingWithApiDatabaseLookupTest.java
@@ -0,0 +1,119 @@
+// Copyright (c) 2024, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.memberrebinding;
+
+import static com.android.tools.r8.apimodel.ApiModelingTestHelper.setMockApiLevelForClass;
+import static com.android.tools.r8.apimodel.ApiModelingTestHelper.setMockApiLevelForMethod;
+import static com.android.tools.r8.utils.codeinspector.CodeMatchers.invokesMethodWithHolderAndName;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.KeepConstantArguments;
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NoMethodStaticizing;
+import com.android.tools.r8.NoParameterTypeStrengthening;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class MemberRebindingWithApiDatabaseLookupTest extends TestBase {
+
+  static final String EXPECTED = "foobar";
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withDexRuntimes().withAllApiLevels().build();
+  }
+
+  public MemberRebindingWithApiDatabaseLookupTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    testForR8(parameters.getBackend())
+        .setMinApi(parameters)
+        .addProgramClasses(Foo.class, Bar.class, ProgramClassExtendsLibrary.class)
+        .addLibraryClasses(LibraryClass.class, LibraryBaseClass.class)
+        .addDefaultRuntimeLibrary(parameters)
+        .enableInliningAnnotations()
+        .enableNeverClassInliningAnnotations()
+        .enableNoMethodStaticizingAnnotations()
+        .enableConstantArgumentAnnotations()
+        .enableNoParameterTypeStrengtheningAnnotations()
+        .addKeepMainRule(Foo.class)
+        .addKeepClassRules(ProgramClassExtendsLibrary.class)
+        .apply(setMockApiLevelForClass(LibraryBaseClass.class, AndroidApiLevel.B))
+        .apply(setMockApiLevelForClass(LibraryClass.class, AndroidApiLevel.L))
+        .apply(
+            setMockApiLevelForMethod(
+                LibraryBaseClass.class.getDeclaredMethod("z"), AndroidApiLevel.B))
+        .compile()
+        .addRunClasspathClasses(LibraryBaseClass.class)
+        .run(parameters.getRuntime(), Foo.class)
+        .assertSuccessWithOutputLines(EXPECTED)
+        .inspect(
+            codeInspector -> {
+              // We should not have rewritten the invoke virtual in X to the base most library class
+              // if we are not on dalvik, otherwise the first library class.
+              Class expectedInvokeClass =
+                  parameters.getApiLevel().isLessThan(AndroidApiLevel.L)
+                      ? LibraryClass.class
+                      : LibraryBaseClass.class;
+              MethodSubject xMethod =
+                  codeInspector.clazz(Bar.class).uniqueMethodWithOriginalName("x");
+              assertThat(
+                  xMethod, invokesMethodWithHolderAndName(expectedInvokeClass.getTypeName(), "z"));
+            });
+  }
+
+  public static class Foo {
+    public static void main(String[] args) {
+      if (System.currentTimeMillis() == 0) {
+        new Bar().x(null);
+      } else {
+        new Bar().y("foobar");
+      }
+    }
+  }
+
+  @NeverClassInline
+  public static class Bar {
+    @NeverInline
+    @NoMethodStaticizing
+    @KeepConstantArguments
+    @NoParameterTypeStrengthening
+    public void x(ProgramClassExtendsLibrary value) {
+      // We need to ensure that we don't rebind this to LibraryBaseClass as that will make dalvik
+      // (incorrectly) hard fail verification even when we don't call this method.
+      // Since the superclass of value is not available at runtime dalvik will lower value to
+      // type object, which we can't use for the invoke virtual on the known library class
+      // LibraryBaseClass.
+      value.z();
+    }
+
+    @NeverInline
+    public void y(String s) {
+      System.out.println(s);
+    }
+  }
+
+  public static class ProgramClassExtendsLibrary extends LibraryClass {}
+
+  public static class LibraryClass extends LibraryBaseClass {}
+
+  public static class LibraryBaseClass {
+    public void z() {
+      System.out.println("z()");
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/regress/Regress302826300.java b/src/test/java/com/android/tools/r8/regress/Regress302826300.java
index f87eb90..d8cda04 100644
--- a/src/test/java/com/android/tools/r8/regress/Regress302826300.java
+++ b/src/test/java/com/android/tools/r8/regress/Regress302826300.java
@@ -31,6 +31,9 @@
 
   @Test
   public void testD8() throws Exception {
+    // This is illustrating the problem from b/302826300 using just D8 (in which case we don't
+    // introduce the error, the error is in the build setup). The actual bug is introduced by
+    // R8, see MemberRebindingWithApiDatabaseLookupTest.
     D8TestRunResult run =
         testForD8(parameters.getBackend())
             // We simply pass LibraryBaseClass as program, but could also compile it separately and