diff --git a/src/main/java/com/android/tools/r8/graph/AppInfo.java b/src/main/java/com/android/tools/r8/graph/AppInfo.java
index 9dcd701..612d280 100644
--- a/src/main/java/com/android/tools/r8/graph/AppInfo.java
+++ b/src/main/java/com/android/tools/r8/graph/AppInfo.java
@@ -54,6 +54,10 @@
     return app.classes();
   }
 
+  public Iterable<DexProgramClass> classesWithDeterministicOrder() {
+    return app.classesWithDeterministicOrder();
+  }
+
   public DexClass definitionFor(DexType type) {
     return app.definitionFor(type);
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexApplication.java b/src/main/java/com/android/tools/r8/graph/DexApplication.java
index 8b2fee9..20949c3 100644
--- a/src/main/java/com/android/tools/r8/graph/DexApplication.java
+++ b/src/main/java/com/android/tools/r8/graph/DexApplication.java
@@ -77,6 +77,14 @@
     return classes;
   }
 
+  public Iterable<DexProgramClass> classesWithDeterministicOrder() {
+    programClasses.forceLoad(type -> true);
+    List<DexProgramClass> classes = programClasses.getAllClasses();
+    // To keep the order deterministic, we sort the classes by their type, which is a unique key.
+    classes.sort((a, b) -> a.type.slowCompareTo(b.type));
+    return classes;
+  }
+
   public abstract DexClass definitionFor(DexType type);
 
   public DexProgramClass programDefinitionFor(DexType type) {
diff --git a/src/main/java/com/android/tools/r8/graph/DexType.java b/src/main/java/com/android/tools/r8/graph/DexType.java
index 9983f29..6544ea9 100644
--- a/src/main/java/com/android/tools/r8/graph/DexType.java
+++ b/src/main/java/com/android/tools/r8/graph/DexType.java
@@ -14,6 +14,7 @@
 import java.util.Arrays;
 import java.util.Deque;
 import java.util.Set;
+import java.util.TreeSet;
 import java.util.function.Consumer;
 import java.util.function.Function;
 
@@ -30,6 +31,10 @@
   public final DexString descriptor;
   private String toStringCache = null;
   private int hierarchyLevel = UNKNOWN_LEVEL;
+  /**
+   * Set of direct subtypes. This set has to remain sorted to ensure determinism. The actual sorting
+   * is not important but {@link #slowCompareTo(DexType)} works well.
+   */
   private Set<DexType> directSubtypes = NO_DIRECT_SUBTYPE;
 
   DexType(DexString descriptor) {
@@ -52,7 +57,7 @@
 
   private void ensureDirectSubTypeSet() {
     if (directSubtypes == NO_DIRECT_SUBTYPE) {
-      directSubtypes = Sets.newIdentityHashSet();
+      directSubtypes = new TreeSet<>(DexType::slowCompareTo);
     }
   }
 
diff --git a/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java b/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
index 5a743b5..ff50c3e 100644
--- a/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
@@ -80,7 +80,8 @@
   }
 
   Map<DexType, DexString> computeRenaming(Timing timing) {
-    Iterable<DexProgramClass> classes = appInfo.classes();
+    // Use deterministic class order to make sure renaming is deterministic.
+    Iterable<DexProgramClass> classes = appInfo.classesWithDeterministicOrder();
     // Collect names we have to keep.
     timing.begin("reserve");
     for (DexClass clazz : classes) {
diff --git a/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10TreeShakeJarVerificationTest.java b/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10TreeShakeJarVerificationTest.java
index 766de9d..ae470c6 100644
--- a/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10TreeShakeJarVerificationTest.java
+++ b/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10TreeShakeJarVerificationTest.java
@@ -5,7 +5,6 @@
 
 import com.android.tools.r8.CompilationMode;
 import com.android.tools.r8.utils.AndroidApp;
-import com.android.tools.r8.utils.InternalOptions;
 import org.junit.Test;
 
 public class R8GMSCoreV10TreeShakeJarVerificationTest
@@ -14,24 +13,10 @@
   @Test
   public void buildAndTreeShakeFromDeployJar() throws Exception {
     // TODO(tamaskenez): set hasReference = true when we have the noshrink file for V10
-    buildAndTreeShakeFromDeployJar(
-        CompilationMode.RELEASE, GMSCORE_V10_DIR, false, GMSCORE_V10_MAX_SIZE, null);
-  }
-
-  private void configureDeterministic(InternalOptions options) {
-    options.skipMinification = true;
-  }
-
-  @Test
-  public void deterministic() throws Exception {
-    // TODO(sgjesse): When minification is deterministic remove this test and make the one above
-    // check for deterministic output.
     AndroidApp app1 = buildAndTreeShakeFromDeployJar(
-        CompilationMode.RELEASE, GMSCORE_V10_DIR, false, GMSCORE_V10_MAX_SIZE + 2000000,
-        this::configureDeterministic);
+        CompilationMode.RELEASE, GMSCORE_V10_DIR, false, GMSCORE_V10_MAX_SIZE, null);
     AndroidApp app2 = buildAndTreeShakeFromDeployJar(
-        CompilationMode.RELEASE, GMSCORE_V10_DIR, false, GMSCORE_V10_MAX_SIZE + 2000000,
-        this::configureDeterministic);
+        CompilationMode.RELEASE, GMSCORE_V10_DIR, false, GMSCORE_V10_MAX_SIZE, null);
 
     // Verify that the result of the two compilations was the same.
     assertIdenticalApplications(app1, app2);