diff --git a/src/main/java/com/android/tools/r8/DexIndexedConsumer.java b/src/main/java/com/android/tools/r8/DexIndexedConsumer.java
index 118df2e..e235e67 100644
--- a/src/main/java/com/android/tools/r8/DexIndexedConsumer.java
+++ b/src/main/java/com/android/tools/r8/DexIndexedConsumer.java
@@ -160,7 +160,7 @@
     public void accept(
         int fileIndex, ByteDataView data, Set<String> descriptors, DiagnosticsHandler handler) {
       super.accept(fileIndex, data, descriptors, handler);
-      outputBuilder.addFile(getDexFileName(fileIndex), data, handler);
+      outputBuilder.addIndexedClassFile(fileIndex, getDexFileName(fileIndex), data, handler);
     }
 
     @Override
diff --git a/src/main/java/com/android/tools/r8/utils/ArchiveBuilder.java b/src/main/java/com/android/tools/r8/utils/ArchiveBuilder.java
index 4111bed..69d65ea 100644
--- a/src/main/java/com/android/tools/r8/utils/ArchiveBuilder.java
+++ b/src/main/java/com/android/tools/r8/utils/ArchiveBuilder.java
@@ -17,6 +17,10 @@
 import java.nio.file.Files;
 import java.nio.file.Path;
 import java.nio.file.StandardOpenOption;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.SortedSet;
+import java.util.TreeSet;
 import java.util.zip.ZipEntry;
 import java.util.zip.ZipException;
 import java.util.zip.ZipOutputStream;
@@ -27,6 +31,9 @@
   private ZipOutputStream stream = null;
   private boolean closed = false;
   private int openCount = 0;
+  private int classesFileIndex = 0;
+  private Map<Integer, DelayedData> delayedClassesDexFiles = new HashMap<>();
+  private SortedSet<DelayedData> delayedWrites = new TreeSet<>();
 
   public ArchiveBuilder(Path archive) {
     this.archive = archive;
@@ -44,6 +51,7 @@
     assert !closed;
     openCount--;
     if (openCount == 0) {
+      writeDelayed(handler);
       closed = true;
       try {
         getStreamRaw().close();
@@ -54,6 +62,20 @@
     }
   }
 
+  private void writeDelayed(DiagnosticsHandler handler) {
+    // We should never have any indexed files at this point
+    assert delayedClassesDexFiles.isEmpty();
+    for (DelayedData data : delayedWrites) {
+      if (data.isDirectory) {
+        assert data.content == null;
+        writeDirectoryNow(data.name, handler);
+      } else {
+        assert data.content != null;
+        writeFileNow(data.name, data.content, handler);
+      }
+    }
+  }
+
   private ZipOutputStream getStreamRaw() throws IOException {
     if (stream != null) {
       return stream;
@@ -85,7 +107,11 @@
   }
 
   @Override
-  public void addDirectory(String name, DiagnosticsHandler handler) {
+  public synchronized void addDirectory(String name, DiagnosticsHandler handler) {
+    delayedWrites.add(DelayedData.createDirectory(name));
+  }
+
+  private void writeDirectoryNow(String name, DiagnosticsHandler handler) {
     if (name.charAt(name.length() - 1) != DataResource.SEPARATOR) {
       name += DataResource.SEPARATOR;
     }
@@ -105,7 +131,10 @@
   @Override
   public void addFile(String name, DataEntryResource content, DiagnosticsHandler handler) {
     try (InputStream in = content.getByteStream()) {
-      addFile(name, ByteDataView.of(ByteStreams.toByteArray(in)), handler);
+      ByteDataView view = ByteDataView.of(ByteStreams.toByteArray(in));
+      synchronized (this) {
+        delayedWrites.add(DelayedData.createFile(name, view));
+      }
     } catch (IOException e) {
       handleIOException(e, handler);
     } catch (ResourceException e) {
@@ -116,6 +145,10 @@
 
   @Override
   public synchronized void addFile(String name, ByteDataView content, DiagnosticsHandler handler) {
+    delayedWrites.add(DelayedData.createFile(name,  ByteDataView.of(content.copyByteData())));
+  }
+
+  private void writeFileNow(String name, ByteDataView content, DiagnosticsHandler handler) {
     try {
       ZipUtils.writeToZipStream(getStream(handler), name, content, ZipEntry.STORED);
     } catch (IOException e) {
@@ -123,6 +156,30 @@
     }
   }
 
+  private void writeNextIfAvailable(DiagnosticsHandler handler) {
+    DelayedData data = delayedClassesDexFiles.remove(classesFileIndex);
+    while (data != null) {
+      writeFileNow(data.name, data.content, handler);
+      classesFileIndex++;
+      data = delayedClassesDexFiles.remove(classesFileIndex);
+    }
+  }
+
+  @Override
+  public synchronized void addIndexedClassFile(
+      int index, String name, ByteDataView content, DiagnosticsHandler handler) {
+    if (index == classesFileIndex) {
+      // Fast case, we got the file in order (or we only had one).
+      writeFileNow(name, content, handler);
+      classesFileIndex++;
+      writeNextIfAvailable(handler);
+    } else {
+      // Data is released in the application writer, take a copy.
+      delayedClassesDexFiles.put(index,
+          new DelayedData(name, ByteDataView.of(content.copyByteData()), false));
+    }
+  }
+
   @Override
   public Origin getOrigin() {
     return origin;
@@ -132,4 +189,32 @@
   public Path getPath() {
     return archive;
   }
+
+  private static class DelayedData implements Comparable<DelayedData> {
+    public final String name;
+    public final ByteDataView content;
+    public final boolean isDirectory;
+
+    public static DelayedData createFile(String name, ByteDataView content) {
+      return new DelayedData(name, content, false);
+    }
+
+    public static DelayedData createDirectory(String name) {
+      return new DelayedData(name, null, true);
+    }
+
+    private DelayedData(String name, ByteDataView content, boolean isDirectory) {
+      this.name = name;
+      this.content = content;
+      this.isDirectory = isDirectory;
+    }
+
+    @Override
+    public int compareTo(DelayedData other) {
+      if (other == null) {
+        return name.compareTo(null);
+      }
+      return name.compareTo(other.name);
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/utils/DirectoryBuilder.java b/src/main/java/com/android/tools/r8/utils/DirectoryBuilder.java
index 8e0b054..f78983f 100644
--- a/src/main/java/com/android/tools/r8/utils/DirectoryBuilder.java
+++ b/src/main/java/com/android/tools/r8/utils/DirectoryBuilder.java
@@ -68,6 +68,12 @@
   }
 
   @Override
+  public void addIndexedClassFile(
+      int index, String name, ByteDataView content, DiagnosticsHandler handler) {
+    addFile(name, content, handler);
+  }
+
+  @Override
   public Origin getOrigin() {
     return origin;
   }
diff --git a/src/main/java/com/android/tools/r8/utils/OutputBuilder.java b/src/main/java/com/android/tools/r8/utils/OutputBuilder.java
index 9077f7b..be739e3 100644
--- a/src/main/java/com/android/tools/r8/utils/OutputBuilder.java
+++ b/src/main/java/com/android/tools/r8/utils/OutputBuilder.java
@@ -23,6 +23,9 @@
 
   void addFile(String name, ByteDataView content, DiagnosticsHandler handler);
 
+  void addIndexedClassFile(
+      int index, String name, ByteDataView content, DiagnosticsHandler handler);
+
   Path getPath();
 
   Origin getOrigin();
diff --git a/src/test/java/com/android/tools/r8/internal/CompilationTestBase.java b/src/test/java/com/android/tools/r8/internal/CompilationTestBase.java
index e26ec3d..be14412 100644
--- a/src/test/java/com/android/tools/r8/internal/CompilationTestBase.java
+++ b/src/test/java/com/android/tools/r8/internal/CompilationTestBase.java
@@ -19,6 +19,7 @@
 import com.android.tools.r8.R8RunArtTestsTest.CompilerUnderTest;
 import com.android.tools.r8.ResourceException;
 import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.dex.ApplicationWriter;
 import com.android.tools.r8.naming.MemberNaming.FieldSignature;
 import com.android.tools.r8.naming.MemberNaming.MethodSignature;
 import com.android.tools.r8.utils.AndroidApiLevel;
@@ -43,13 +44,18 @@
 import java.nio.file.Path;
 import java.nio.file.Paths;
 import java.util.Collections;
+import java.util.Enumeration;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.concurrent.ExecutionException;
 import java.util.function.BiConsumer;
 import java.util.function.Consumer;
+import java.util.function.Supplier;
 import java.util.stream.Collectors;
+import java.util.zip.ZipEntry;
+import java.util.zip.ZipFile;
+import org.junit.Assert;
 import org.junit.Before;
 import org.junit.ComparisonFailure;
 import org.junit.Rule;
@@ -89,6 +95,22 @@
     return result;
   }
 
+  public void assertIdenticalZipFiles(File file1, File file2) throws IOException {
+    try (ZipFile zipFile1 = new ZipFile(file1); ZipFile zipFile2 = new ZipFile(file2)) {
+      final Enumeration<? extends ZipEntry> entries1 = zipFile1.entries();
+      final Enumeration<? extends ZipEntry> entries2 = zipFile2.entries();
+
+      while (entries1.hasMoreElements()) {
+        Assert.assertTrue(entries2.hasMoreElements());
+        ZipEntry entry1 = entries1.nextElement();
+        ZipEntry entry2 = entries2.nextElement();
+        Assert.assertEquals(entry1.getName(), entry2.getName());
+        Assert.assertEquals(entry1.getCrc(), entry2.getCrc());
+        Assert.assertEquals(entry1.getSize(), entry2.getSize());
+      }
+    }
+  }
+
   public AndroidApp runAndCheckVerification(
       CompilerUnderTest compiler,
       CompilationMode mode,
@@ -97,6 +119,19 @@
       Consumer<InternalOptions> optionsConsumer,
       List<String> inputs)
       throws ExecutionException, IOException, CompilationFailedException {
+    return runAndCheckVerification(compiler, mode, referenceApk, pgConfs, optionsConsumer,
+        DexIndexedConsumer::emptyConsumer, inputs);
+  }
+
+  public AndroidApp runAndCheckVerification(
+      CompilerUnderTest compiler,
+      CompilationMode mode,
+      String referenceApk,
+      List<String> pgConfs,
+      Consumer<InternalOptions> optionsConsumer,
+      Supplier<DexIndexedConsumer> dexIndexedConsumerSupplier,
+      List<String> inputs)
+      throws ExecutionException, IOException, CompilationFailedException {
     assertTrue(referenceApk == null || new File(referenceApk).exists());
     AndroidAppConsumers outputApp;
     if (compiler == CompilerUnderTest.R8) {
@@ -107,7 +142,7 @@
             pgConfs.stream().map(Paths::get).collect(Collectors.toList()));
       }
       builder.setMode(mode);
-      builder.setProgramConsumer(DexIndexedConsumer.emptyConsumer());
+      builder.setProgramConsumer(dexIndexedConsumerSupplier.get());
       builder.setMinApiLevel(AndroidApiLevel.L.getLevel());
       ToolHelper.allowPartiallyImplementedProguardOptions(builder);
       ToolHelper.addProguardConfigurationConsumer(
@@ -131,6 +166,7 @@
     return checkVerification(outputApp.build(), referenceApk);
   }
 
+
   public AndroidApp checkVerification(AndroidApp outputApp, String referenceApk)
       throws IOException, ExecutionException {
     Path out = temp.getRoot().toPath().resolve("all.zip");
diff --git a/src/test/java/com/android/tools/r8/internal/GMSCoreDeployJarVerificationTest.java b/src/test/java/com/android/tools/r8/internal/GMSCoreDeployJarVerificationTest.java
index 09ce657..634ff6f 100644
--- a/src/test/java/com/android/tools/r8/internal/GMSCoreDeployJarVerificationTest.java
+++ b/src/test/java/com/android/tools/r8/internal/GMSCoreDeployJarVerificationTest.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.CompilationFailedException;
 import com.android.tools.r8.CompilationMode;
+import com.android.tools.r8.DexIndexedConsumer;
 import com.android.tools.r8.R8RunArtTestsTest.CompilerUnderTest;
 import com.android.tools.r8.shaking.ProguardRuleParserException;
 import com.android.tools.r8.utils.AndroidApp;
@@ -13,6 +14,7 @@
 import java.util.Collections;
 import java.util.concurrent.ExecutionException;
 import java.util.function.Consumer;
+import java.util.function.Supplier;
 
 public class GMSCoreDeployJarVerificationTest extends GMSCoreCompilationTestBase {
 
@@ -38,4 +40,20 @@
         optionsConsumer,
         Collections.singletonList(base + DEPLOY_JAR));
   }
+
+  public AndroidApp buildFromDeployJar(
+      CompilerUnderTest compiler, CompilationMode mode, String base, boolean hasReference,
+      Consumer<InternalOptions> optionsConsumer, Supplier<DexIndexedConsumer> consumerSupplier)
+      throws ExecutionException, IOException, ProguardRuleParserException,
+      CompilationFailedException {
+    return runAndCheckVerification(
+        compiler,
+        mode,
+        hasReference ? base + REFERENCE_APK : null,
+        null,
+        optionsConsumer,
+        consumerSupplier,
+        Collections.singletonList(base + DEPLOY_JAR));
+  }
+
 }
diff --git a/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10DeployJarVerificationTest.java b/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10DeployJarVerificationTest.java
index d881185..5803355 100644
--- a/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10DeployJarVerificationTest.java
+++ b/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10DeployJarVerificationTest.java
@@ -7,8 +7,12 @@
 import static org.junit.Assert.assertEquals;
 
 import com.android.tools.r8.CompilationMode;
+import com.android.tools.r8.DexIndexedConsumer;
+import com.android.tools.r8.DexIndexedConsumer.ArchiveConsumer;
 import com.android.tools.r8.R8RunArtTestsTest.CompilerUnderTest;
 import com.android.tools.r8.utils.AndroidApp;
+import java.io.File;
+import java.util.function.Supplier;
 import org.junit.Test;
 
 public class R8GMSCoreV10DeployJarVerificationTest extends GMSCoreDeployJarVerificationTest {
@@ -19,6 +23,9 @@
   @Test
   public void buildFromDeployJar() throws Exception {
     // TODO(tamaskenez): set hasReference = true when we have the noshrink file for V10
+    File tempFolder = temp.newFolder();
+    File app1Zip = new File(tempFolder, "app1.zip");
+    File app2Zip = new File(tempFolder, "app2.zip");
     AndroidApp app1 =
         buildFromDeployJar(
             CompilerUnderTest.R8,
@@ -27,7 +34,8 @@
             false,
             options ->
                 options.proguardMapConsumer =
-                    (proguardMap, handler) -> this.proguardMap1 = proguardMap);
+                    (proguardMap, handler) -> this.proguardMap1 = proguardMap,
+            ()-> new ArchiveConsumer(app1Zip.toPath(), true));
     AndroidApp app2 =
         buildFromDeployJar(
             CompilerUnderTest.R8,
@@ -36,10 +44,14 @@
             false,
             options ->
                 options.proguardMapConsumer =
-                    (proguardMap, handler) -> this.proguardMap2 = proguardMap);
+                    (proguardMap, handler) -> this.proguardMap2 = proguardMap,
+            ()-> new ArchiveConsumer(app2Zip.toPath(), true));
+
+
 
     // Verify that the result of the two compilations was the same.
     assertIdenticalApplications(app1, app2);
+    assertIdenticalZipFiles(app1Zip, app2Zip);
     assertEquals(proguardMap1, proguardMap2);
   }
 }
diff --git a/src/test/java/com/android/tools/r8/maindexlist/MainDexTracingTest.java b/src/test/java/com/android/tools/r8/maindexlist/MainDexTracingTest.java
index ddb0e7d..e013b02 100644
--- a/src/test/java/com/android/tools/r8/maindexlist/MainDexTracingTest.java
+++ b/src/test/java/com/android/tools/r8/maindexlist/MainDexTracingTest.java
@@ -20,15 +20,21 @@
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.StringUtils;
 import java.io.ByteArrayOutputStream;
+import java.io.IOException;
 import java.io.PrintStream;
 import java.nio.charset.Charset;
 import java.nio.charset.StandardCharsets;
 import java.nio.file.Files;
 import java.nio.file.Path;
 import java.nio.file.Paths;
+import java.util.Arrays;
+import java.util.Enumeration;
+import java.util.LinkedList;
 import java.util.List;
 import java.util.function.Consumer;
 import java.util.stream.Collectors;
+import java.util.zip.ZipEntry;
+import java.util.zip.ZipFile;
 import org.junit.Assert;
 import org.junit.Test;
 
@@ -301,6 +307,34 @@
         nonLambdaOffset++;
       }
     }
+    testZipfileOrder(out);
+  }
+
+  private void testZipfileOrder(Path out) throws IOException {
+    // Sanity check that the classes.dex files are in the correct order
+    ZipFile outZip = new ZipFile(out.toFile());
+    Enumeration<? extends ZipEntry> entries = outZip.entries();
+    int index = 0;
+    LinkedList<String> entryNames = new LinkedList<>();
+    // We expect classes*.dex files first, in order, then the rest of the files, in order.
+    while(entries.hasMoreElements()) {
+      ZipEntry entry = entries.nextElement();
+      if (!entry.getName().startsWith("classes") || !entry.getName().endsWith(".dex")) {
+        entryNames.add(entry.getName());
+        continue;
+      }
+      if (index == 0) {
+        Assert.assertEquals("classes.dex", entry.getName());
+      } else {
+        Assert.assertEquals("classes" + (index + 1) + ".dex", entry.getName());
+      }
+      index++;
+    }
+    // Everything else should be sorted according to name.
+    String[] entriesUnsorted = entryNames.toArray(new String[0]);
+    String[] entriesSorted = entryNames.toArray(new String[0]);
+    Arrays.sort(entriesSorted);
+    Assert.assertArrayEquals(entriesUnsorted, entriesSorted);
   }
 
   private boolean isLambda(String mainDexEntry) {