diff --git a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
index 08722c3..b11e33d 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -207,9 +207,13 @@
     return true;
   }
 
-  private boolean mergeMayLeadToIllegalAccesses(DexClass clazz, DexClass singleSubclass) {
-    if (clazz.type.isSamePackage(singleSubclass.type)) {
-      return false;
+  private boolean mergeMayLeadToIllegalAccesses(DexClass source, DexClass target) {
+    if (source.type.isSamePackage(target.type)) {
+      int accessLevel =
+          source.accessFlags.isPrivate() ? 0 : (source.accessFlags.isPublic() ? 2 : 1);
+      int otherAccessLevel =
+          target.accessFlags.isPrivate() ? 0 : (target.accessFlags.isPublic() ? 2 : 1);
+      return accessLevel > otherAccessLevel;
     }
     // TODO(christofferqa): To merge [clazz] into a class from another package we need to ensure:
     // (A) All accesses to [clazz] and its members from inside the current package of [clazz] will
diff --git a/src/test/examples/classmerging/SimpleInterface.java b/src/test/examples/classmerging/SimpleInterface.java
deleted file mode 100644
index e8ebcab..0000000
--- a/src/test/examples/classmerging/SimpleInterface.java
+++ /dev/null
@@ -1,9 +0,0 @@
-// Copyright (c) 2018, 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 classmerging;
-
-public interface SimpleInterface {
-  void foo();
-}
diff --git a/src/test/examples/classmerging/SimpleInterfaceAccessTest.java b/src/test/examples/classmerging/SimpleInterfaceAccessTest.java
index 04b5386..ce7bf14 100644
--- a/src/test/examples/classmerging/SimpleInterfaceAccessTest.java
+++ b/src/test/examples/classmerging/SimpleInterfaceAccessTest.java
@@ -8,9 +8,35 @@
 
 public class SimpleInterfaceAccessTest {
   public static void main(String[] args) {
-    // It is not possible to merge the interface SimpleInterface into SimpleInterfaceImpl, since
-    // this would lead to an illegal class access here.
-    SimpleInterface obj = SimpleInterfaceImplRetriever.getSimpleInterfaceImpl();
-    obj.foo();
+    // Without access modifications, it is not possible to merge the interface SimpleInterface into
+    // SimpleInterfaceImpl, since this would lead to an illegal class access here.
+    SimpleInterface x = SimpleInterfaceImplRetriever.getSimpleInterfaceImpl();
+    x.foo();
+
+    // Without access modifications, it is not possible to merge the interface OtherSimpleInterface
+    // into OtherSimpleInterfaceImpl, since this could lead to an illegal class access if another
+    // package references OtherSimpleInterface.
+    OtherSimpleInterface y = new OtherSimpleInterfaceImpl();
+    y.bar();
+  }
+
+  // Should only be merged into OtherSimpleInterfaceImpl if access modifications are allowed.
+  public interface SimpleInterface {
+
+    void foo();
+  }
+
+  // Should only be merged into OtherSimpleInterfaceImpl if access modifications are allowed.
+  public interface OtherSimpleInterface {
+
+    void bar();
+  }
+
+  private static class OtherSimpleInterfaceImpl implements OtherSimpleInterface {
+
+    @Override
+    public void bar() {
+      System.out.println("In bar on OtherSimpleInterfaceImpl");
+    }
   }
 }
diff --git a/src/test/examples/classmerging/pkg/SimpleInterfaceImplRetriever.java b/src/test/examples/classmerging/pkg/SimpleInterfaceImplRetriever.java
index 5cfa11e..22391e9 100644
--- a/src/test/examples/classmerging/pkg/SimpleInterfaceImplRetriever.java
+++ b/src/test/examples/classmerging/pkg/SimpleInterfaceImplRetriever.java
@@ -4,7 +4,7 @@
 
 package classmerging.pkg;
 
-import classmerging.SimpleInterface;
+import classmerging.SimpleInterfaceAccessTest.SimpleInterface;
 
 public class SimpleInterfaceImplRetriever {
 
diff --git a/src/test/java/com/android/tools/r8/classmerging/ClassMergingTest.java b/src/test/java/com/android/tools/r8/classmerging/ClassMergingTest.java
index 2e983bd..f141d36 100644
--- a/src/test/java/com/android/tools/r8/classmerging/ClassMergingTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/ClassMergingTest.java
@@ -36,7 +36,6 @@
 import java.util.concurrent.ExecutionException;
 import java.util.function.Consumer;
 import java.util.function.Predicate;
-import org.junit.Ignore;
 import org.junit.Test;
 
 // TODO(christofferqa): Add tests to check that statically typed invocations on method handles
@@ -270,8 +269,10 @@
     String main = "classmerging.SimpleInterfaceAccessTest";
     Path[] programFiles =
         new Path[] {
-          CF_DIR.resolve("SimpleInterface.class"),
           CF_DIR.resolve("SimpleInterfaceAccessTest.class"),
+          CF_DIR.resolve("SimpleInterfaceAccessTest$SimpleInterface.class"),
+          CF_DIR.resolve("SimpleInterfaceAccessTest$OtherSimpleInterface.class"),
+          CF_DIR.resolve("SimpleInterfaceAccessTest$OtherSimpleInterfaceImpl.class"),
           CF_DIR.resolve("pkg/SimpleInterfaceImplRetriever.class"),
           CF_DIR.resolve("pkg/SimpleInterfaceImplRetriever$SimpleInterfaceImpl.class")
         };
@@ -279,14 +280,15 @@
     // is in a different package and is not public.
     ImmutableSet<String> preservedClassNames =
         ImmutableSet.of(
-            "classmerging.SimpleInterface",
             "classmerging.SimpleInterfaceAccessTest",
+            "classmerging.SimpleInterfaceAccessTest$SimpleInterface",
+            "classmerging.SimpleInterfaceAccessTest$OtherSimpleInterface",
+            "classmerging.SimpleInterfaceAccessTest$OtherSimpleInterfaceImpl",
             "classmerging.pkg.SimpleInterfaceImplRetriever",
             "classmerging.pkg.SimpleInterfaceImplRetriever$SimpleInterfaceImpl");
     runTest(main, programFiles, preservedClassNames::contains);
   }
 
-  @Ignore("b/73958515")
   @Test
   public void testNoIllegalClassAccessWithAccessModifications() throws Exception {
     // If access modifications are allowed then SimpleInterface should be merged into
@@ -294,14 +296,20 @@
     String main = "classmerging.SimpleInterfaceAccessTest";
     Path[] programFiles =
         new Path[] {
-          CF_DIR.resolve("SimpleInterface.class"),
           CF_DIR.resolve("SimpleInterfaceAccessTest.class"),
+          CF_DIR.resolve("SimpleInterfaceAccessTest$SimpleInterface.class"),
+          CF_DIR.resolve("SimpleInterfaceAccessTest$OtherSimpleInterface.class"),
+          CF_DIR.resolve("SimpleInterfaceAccessTest$OtherSimpleInterfaceImpl.class"),
           CF_DIR.resolve("pkg/SimpleInterfaceImplRetriever.class"),
           CF_DIR.resolve("pkg/SimpleInterfaceImplRetriever$SimpleInterfaceImpl.class")
         };
     ImmutableSet<String> preservedClassNames =
         ImmutableSet.of(
             "classmerging.SimpleInterfaceAccessTest",
+            // TODO(christofferqa): Should be able to merge SimpleInterface into SimpleInterfaceImpl
+            // when access modifications are allowed.
+            "classmerging.SimpleInterfaceAccessTest$SimpleInterface",
+            "classmerging.SimpleInterfaceAccessTest$OtherSimpleInterfaceImpl",
             "classmerging.pkg.SimpleInterfaceImplRetriever",
             "classmerging.pkg.SimpleInterfaceImplRetriever$SimpleInterfaceImpl");
     // Allow access modifications (and prevent SimpleInterfaceImplRetriever from being removed as