diff --git a/src/main/java/com/android/tools/r8/ResourceShrinker.java b/src/main/java/com/android/tools/r8/ResourceShrinker.java
index 77abde6..fad1f4c 100644
--- a/src/main/java/com/android/tools/r8/ResourceShrinker.java
+++ b/src/main/java/com/android/tools/r8/ResourceShrinker.java
@@ -244,7 +244,7 @@
               .flatMap(f -> f.annotations().stream());
       Stream<DexAnnotation> methodAnnotations =
           Streams.stream(classDef.methods())
-              .filter(DexEncodedMethod::hasAnnotation)
+              .filter(DexEncodedMethod::hasAnyAnnotations)
               .flatMap(m -> m.annotations().stream());
 
       Streams.concat(classAnnotations, fieldAnnotations, methodAnnotations)
diff --git a/src/main/java/com/android/tools/r8/graph/DexDefinition.java b/src/main/java/com/android/tools/r8/graph/DexDefinition.java
index 8eeda6b..155abe7 100644
--- a/src/main/java/com/android/tools/r8/graph/DexDefinition.java
+++ b/src/main/java/com/android/tools/r8/graph/DexDefinition.java
@@ -25,6 +25,11 @@
     return !annotations().isEmpty();
   }
 
+  // Also returns true if a method has parameter annotations.
+  public boolean hasAnyAnnotations() {
+    return hasAnnotations();
+  }
+
   public DexAnnotationSet annotations() {
     return annotations;
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
index 60c0ec6..986b709 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -890,6 +890,11 @@
     return builder.toString();
   }
 
+  @Override
+  public boolean hasAnyAnnotations() {
+    return hasAnnotations() || hasParameterAnnotations();
+  }
+
   public ParameterAnnotationsList getParameterAnnotations() {
     return parameterAnnotationsList;
   }
@@ -898,6 +903,10 @@
     parameterAnnotationsList = ParameterAnnotationsList.empty();
   }
 
+  public boolean hasParameterAnnotations() {
+    return !getParameterAnnotations().isEmpty();
+  }
+
   public String toSmaliString(ClassNameMapper naming) {
     checkIfObsolete();
     StringBuilder builder = new StringBuilder();
@@ -1458,11 +1467,6 @@
     return this;
   }
 
-  public boolean hasAnnotation() {
-    checkIfObsolete();
-    return !annotations().isEmpty() || !parameterAnnotationsList.isEmpty();
-  }
-
   public static int slowCompare(DexEncodedMethod m1, DexEncodedMethod m2) {
     return m1.getReference().compareTo(m2.getReference());
   }
diff --git a/src/main/java/com/android/tools/r8/graph/MethodCollection.java b/src/main/java/com/android/tools/r8/graph/MethodCollection.java
index 35e0541..d445f9f 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodCollection.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodCollection.java
@@ -321,7 +321,7 @@
   public boolean hasAnnotations() {
     return traverse(
             method ->
-                method.hasAnnotation()
+                method.hasAnyAnnotations()
                     ? TraversalContinuation.BREAK
                     : TraversalContinuation.CONTINUE)
         .shouldBreak();
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/RespectPackageBoundaries.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/RespectPackageBoundaries.java
index 8f59c36..6e9e19f 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/RespectPackageBoundaries.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/RespectPackageBoundaries.java
@@ -6,12 +6,16 @@
 
 import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexDefinition;
 import com.android.tools.r8.graph.DexEncodedMember;
 import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.horizontalclassmerging.MergeGroup;
 import com.android.tools.r8.horizontalclassmerging.MultiClassPolicy;
 import com.android.tools.r8.shaking.VerticalClassMerger.IllegalAccessDetector;
 import com.android.tools.r8.utils.TraversalContinuation;
+import com.google.common.collect.Iterables;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.LinkedHashMap;
@@ -31,6 +35,26 @@
       return true;
     }
 
+    // Annotations may access non-public items (or themselves be non-public), so for now we
+    // conservatively restrict class merging when annotations are present.
+    //
+    // Note that in non-compat mode we should never see any annotations here, since we only merge
+    // non-kept classes with non-kept members.
+    if (clazz.hasAnnotations()
+        || Iterables.any(clazz.members(), DexDefinition::hasAnyAnnotations)) {
+      return true;
+    }
+
+    // Check that each implemented interface is public.
+    for (DexType interfaceType : clazz.getInterfaces()) {
+      if (clazz.getType().isSamePackage(interfaceType)) {
+        DexClass interfaceClass = appView.definitionFor(interfaceType);
+        if (interfaceClass == null || !interfaceClass.isPublic()) {
+          return true;
+        }
+      }
+    }
+
     // If any members are package private or protected, then their access depends on the package.
     for (DexEncodedMember<?, ?> member : clazz.members()) {
       if (member.getAccessFlags().isPackagePrivateOrProtected()) {
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/InterfacesVisibilityTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/InterfacesVisibilityTest.java
index b5d7af1..b03e236 100644
--- a/src/test/java/com/android/tools/r8/classmerging/horizontal/InterfacesVisibilityTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/InterfacesVisibilityTest.java
@@ -7,6 +7,7 @@
 import static com.android.tools.r8.utils.codeinspector.Matchers.isImplementing;
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
 import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertTrue;
 
 import com.android.tools.r8.NeverClassInline;
 import com.android.tools.r8.NeverInline;
@@ -14,6 +15,7 @@
 import com.android.tools.r8.classmerging.horizontal.testclasses.InterfacesVisibilityTestClasses;
 import com.android.tools.r8.classmerging.horizontal.testclasses.InterfacesVisibilityTestClasses.ImplementingPackagePrivateInterface;
 import com.android.tools.r8.classmerging.horizontal.testclasses.InterfacesVisibilityTestClasses.Invoker;
+import com.android.tools.r8.utils.codeinspector.HorizontallyMergedClassesInspector;
 import org.junit.Test;
 
 public class InterfacesVisibilityTest extends HorizontalClassMergingTestBase {
@@ -26,31 +28,31 @@
     String packagePrivateInterfaceName =
         InterfacesVisibilityTestClasses.class.getTypeName() + "$PackagePrivateInterface";
     testForR8(parameters.getBackend())
-        .addInnerClasses(getClass())
-        .addProgramClasses(ImplementingPackagePrivateInterface.class, Invoker.class)
-        .addProgramClasses(Class.forName(packagePrivateInterfaceName))
+        .addInnerClasses(getClass(), InterfacesVisibilityTestClasses.class)
         .addKeepMainRule(Main.class)
         .enableInliningAnnotations()
         .enableNeverClassInliningAnnotations()
         .enableNoVerticalClassMergingAnnotations()
         .enableNoHorizontalClassMergingAnnotations()
         .setMinApi(parameters.getApiLevel())
-        // TODO(b/191248536): These classes should not be merged.
         .addHorizontallyMergedClassesInspector(
-            inspector ->
-                inspector.assertMergedInto(ImplementingPackagePrivateInterface.class, A.class))
+            HorizontallyMergedClassesInspector::assertNoClassesMerged)
         .compile()
         .inspect(
             codeInspector -> {
+              // A is present and has no interfaces.
               assertThat(codeInspector.clazz(A.class), isPresent());
-              assertThat(codeInspector.clazz(packagePrivateInterfaceName), isPresent());
+              assertTrue(
+                  codeInspector.clazz(A.class).getDexProgramClass().getInterfaces().isEmpty());
+
+              // ImplementingPackagePrivateInterface is present and implements
+              // PackagePrivateInterface.
               assertThat(
-                  codeInspector.clazz(A.class),
+                  codeInspector.clazz(ImplementingPackagePrivateInterface.class),
                   isImplementing(codeInspector.clazz(packagePrivateInterfaceName)));
             })
         .run(parameters.getRuntime(), Main.class)
-        // TODO(b/191248536) Should be .assertSuccessWithOutputLines("foo", "bar");
-        .assertFailure();
+        .assertSuccessWithOutputLines("foo", "bar");
   }
 
   @NeverClassInline