diff --git a/src/main/java/com/android/tools/r8/graph/DexTypeList.java b/src/main/java/com/android/tools/r8/graph/DexTypeList.java
index 076322a..07410c0 100644
--- a/src/main/java/com/android/tools/r8/graph/DexTypeList.java
+++ b/src/main/java/com/android/tools/r8/graph/DexTypeList.java
@@ -54,6 +54,10 @@
     return values.isEmpty() ? DexTypeList.empty() : new DexTypeList(values);
   }
 
+  public DexType get(int index) {
+    return values[index];
+  }
+
   public DexTypeList keepIf(Predicate<DexType> predicate) {
     DexType[] filtered = ArrayUtils.filter(DexType[].class, values, predicate);
     if (filtered != values) {
diff --git a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
index 997ef55..7578839 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -1758,7 +1758,7 @@
 
     KeepReason reason = KeepReason.reachableFromLiveType(clazz.type);
 
-    for (DexType iface : clazz.interfaces.values) {
+    for (DexType iface : clazz.getInterfaces()) {
       markInterfaceTypeAsLiveViaInheritanceClause(iface, clazz);
     }
 
@@ -1846,31 +1846,38 @@
         || rootSet.noUnusedInterfaceRemoval.contains(type)
         || mode.isMainDexTracing()) {
       markTypeAsLive(clazz, implementer);
-    } else {
-      if (liveTypes.contains(clazz)) {
-        // The interface is already live, so make sure to report this implements-edge.
-        graphReporter.reportClassReferencedFrom(clazz, implementer);
-      } else {
-        // No need to mark the type as live. If an interface type is only reachable via the
-        // inheritance clause of another type it can simply be removed from the inheritance clause.
-        // The interface is needed if it has a live default interface method or field, though.
-        // Therefore, we record that this implemented-by edge has not been reported, such that we
-        // can report it in the future if one its members becomes live.
-        WorkList<DexProgramClass> worklist = WorkList.newIdentityWorkList();
-        worklist.addIfNotSeen(clazz);
-        while (worklist.hasNext()) {
-          DexProgramClass current = worklist.next();
-          if (liveTypes.contains(current)) {
-            continue;
-          }
-          Set<DexProgramClass> implementors =
-              unusedInterfaceTypes.computeIfAbsent(current, ignore -> Sets.newIdentityHashSet());
-          if (implementors.add(implementer)) {
-            for (DexType iface : current.interfaces.values) {
-              DexProgramClass definition = getProgramClassOrNull(iface, current);
-              if (definition != null) {
-                worklist.addIfNotSeen(definition);
-              }
+      return;
+    }
+
+    if (liveTypes.contains(clazz)) {
+      // The interface is already live, so make sure to report this implements-edge.
+      graphReporter.reportClassReferencedFrom(clazz, implementer);
+      return;
+    }
+
+    // No need to mark the type as live. If an interface type is only reachable via the
+    // inheritance clause of another type it can simply be removed from the inheritance clause.
+    // The interface is needed if it has a live default interface method or field, though.
+    // Therefore, we record that this implemented-by edge has not been reported, such that we
+    // can report it in the future if one its members becomes live.
+    WorkList<DexProgramClass> worklist = WorkList.newIdentityWorkList();
+    worklist.addIfNotSeen(clazz);
+    while (worklist.hasNext()) {
+      DexProgramClass current = worklist.next();
+      if (liveTypes.contains(current)) {
+        continue;
+      }
+      Set<DexProgramClass> implementors =
+          unusedInterfaceTypes.computeIfAbsent(current, ignore -> Sets.newIdentityHashSet());
+      if (implementors.add(implementer)) {
+        for (DexType iface : current.getInterfaces()) {
+          DexProgramClass definition = getProgramClassOrNull(iface, current);
+          if (definition != null) {
+            if (definition.isPublic()
+                || implementer.getType().isSamePackage(definition.getType())) {
+              worklist.addIfNotSeen(definition);
+            } else {
+              markTypeAsLive(current, implementer);
             }
           }
         }
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/unusedinterfaces/UnusedInterfaceRemovalPackageBoundaryTest.java b/src/test/java/com/android/tools/r8/ir/optimize/unusedinterfaces/UnusedInterfaceRemovalPackageBoundaryTest.java
new file mode 100644
index 0000000..9c4046d
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/unusedinterfaces/UnusedInterfaceRemovalPackageBoundaryTest.java
@@ -0,0 +1,91 @@
+// Copyright (c) 2019, 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.ir.optimize.unusedinterfaces;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isAbsent;
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NoVerticalClassMerging;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.ir.optimize.unusedinterfaces.testclasses.UnusedInterfaceRemovalPackageBoundaryTestClasses;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class UnusedInterfaceRemovalPackageBoundaryTest extends TestBase {
+
+  private static final Class<?> I_CLASS = UnusedInterfaceRemovalPackageBoundaryTestClasses.getI();
+  private static final Class<?> J_CLASS = UnusedInterfaceRemovalPackageBoundaryTestClasses.J.class;
+
+  private final TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public UnusedInterfaceRemovalPackageBoundaryTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass(), UnusedInterfaceRemovalPackageBoundaryTestClasses.class)
+        .addKeepMainRule(TestClass.class)
+        .addKeepClassRules(I_CLASS)
+        .enableNeverClassInliningAnnotations()
+        .enableNoVerticalClassMergingAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .noMinification()
+        .compile()
+        .inspect(
+            inspector -> {
+              ClassSubject iClassSubject = inspector.clazz(I_CLASS);
+              assertThat(iClassSubject, isPresent());
+
+              ClassSubject jClassSubject = inspector.clazz(J_CLASS);
+              assertThat(jClassSubject, isPresent());
+
+              ClassSubject kClassSubject = inspector.clazz(K.class);
+              assertThat(kClassSubject, isAbsent());
+
+              ClassSubject aClassSubject = inspector.clazz(A.class);
+              assertThat(aClassSubject, isPresent());
+              assertEquals(1, aClassSubject.getDexProgramClass().getInterfaces().size());
+              assertEquals(
+                  jClassSubject.getDexProgramClass().getType(),
+                  aClassSubject.getDexProgramClass().getInterfaces().get(0));
+            })
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutputLines("A");
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      new A();
+    }
+  }
+
+  @NoVerticalClassMerging
+  interface K extends UnusedInterfaceRemovalPackageBoundaryTestClasses.J {}
+
+  @NeverClassInline
+  static class A implements K {
+
+    A() {
+      System.out.println("A");
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/unusedinterfaces/testclasses/UnusedInterfaceRemovalPackageBoundaryTestClasses.java b/src/test/java/com/android/tools/r8/ir/optimize/unusedinterfaces/testclasses/UnusedInterfaceRemovalPackageBoundaryTestClasses.java
new file mode 100644
index 0000000..0b623b2
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/unusedinterfaces/testclasses/UnusedInterfaceRemovalPackageBoundaryTestClasses.java
@@ -0,0 +1,20 @@
+// Copyright (c) 2021, 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.ir.optimize.unusedinterfaces.testclasses;
+
+import com.android.tools.r8.NoVerticalClassMerging;
+
+public class UnusedInterfaceRemovalPackageBoundaryTestClasses {
+
+  @NoVerticalClassMerging
+  interface I {}
+
+  @NoVerticalClassMerging
+  public interface J extends I {}
+
+  public static Class<?> getI() {
+    return I.class;
+  }
+}