--- a/mobile/android/base/java/org/mozilla/gecko/telemetry/stores/TelemetryJSONFilePingStore.java
+++ b/mobile/android/base/java/org/mozilla/gecko/telemetry/stores/TelemetryJSONFilePingStore.java
@@ -26,17 +26,19 @@ import java.io.File;
 import java.io.FileInputStream;
 import java.io.FileNotFoundException;
 import java.io.FileOutputStream;
 import java.io.FilenameFilter;
 import java.io.IOException;
 import java.nio.channels.FileLock;
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.Collections;
 import java.util.Iterator;
+import java.util.List;
 import java.util.Set;
 import java.util.SortedSet;
 import java.util.TreeSet;
 
 /**
  * An implementation of TelemetryPingStore that is backed by JSON files.
  *
  * This implementation seeks simplicity. Each ping to upload is stored in its own file with its doc ID
@@ -65,16 +67,17 @@ public class TelemetryJSONFilePingStore 
     @VisibleForTesting static final int MAX_PING_COUNT = 40; // TODO: value.
 
     // We keep the key names short to reduce storage size impact.
     @VisibleForTesting static final String KEY_PAYLOAD = "p";
     @VisibleForTesting static final String KEY_URL_PATH = "u";
 
     private final File storeDir;
     private final FilenameFilter uuidFilenameFilter;
+    private final FileLastModifiedComparator fileLastModifiedComparator = new FileLastModifiedComparator();
 
     public TelemetryJSONFilePingStore(final File storeDir) {
         this.storeDir = storeDir;
         this.storeDir.mkdirs();
         uuidFilenameFilter = new FilenameRegexFilter(UUIDUtil.UUID_PATTERN);
     }
 
     @VisibleForTesting File getPingFile(final String docID) {
@@ -100,17 +103,17 @@ public class TelemetryJSONFilePingStore 
 
     @Override
     public void maybePrunePings() {
         final File[] files = storeDir.listFiles(uuidFilenameFilter);
         if (files.length < MAX_PING_COUNT) {
             return;
         }
 
-        final SortedSet<File> sortedFiles = new TreeSet<>(new FileLastModifiedComparator());
+        final SortedSet<File> sortedFiles = new TreeSet<>(fileLastModifiedComparator);
         sortedFiles.addAll(Arrays.asList(files));
         deleteSmallestFiles(sortedFiles, files.length - MAX_PING_COUNT);
     }
 
     private void deleteSmallestFiles(final SortedSet<File> files, final int numFilesToRemove) {
         final Iterator<File> it = files.iterator();
         int i = 0;
         while (i < numFilesToRemove) {
@@ -118,18 +121,19 @@ public class TelemetryJSONFilePingStore 
             // Sorted set so we're iterating over ascending files.
             final File file = it.next(); // file count > files to remove so this should not throw.
             file.delete();
         }
     }
 
     @Override
     public ArrayList<TelemetryPing> getAllPings() {
-        final File[] files = storeDir.listFiles(uuidFilenameFilter);
-        final ArrayList<TelemetryPing> out = new ArrayList<>(files.length);
+        final List<File> files = Arrays.asList(storeDir.listFiles(uuidFilenameFilter));
+        Collections.sort(files, fileLastModifiedComparator); // oldest to newest
+        final ArrayList<TelemetryPing> out = new ArrayList<>(files.size());
         for (final File file : files) {
             final JSONObject obj = lockAndReadJSONFromFile(file);
             if (obj == null) {
                 // We log in the method to get the JSONObject if we return null.
                 continue;
             }
 
             try {

--- a/mobile/android/base/java/org/mozilla/gecko/telemetry/stores/TelemetryPingStore.java
+++ b/mobile/android/base/java/org/mozilla/gecko/telemetry/stores/TelemetryPingStore.java
@@ -14,21 +14,24 @@ import java.util.List;
 import java.util.Set;
 
 /**
  * Persistent storage for TelemetryPings that are queued for upload.
  *
  * An implementation of this class is expected to be thread-safe. Additionally,
  * multiple instances can be created and run simultaneously so they must be able
  * to synchronize state (or be stateless!).
+ *
+ * The pings in {@link #getAllPings()} and {@link #maybePrunePings()} are returned in the
+ * same order in order to guarantee consistent results.
  */
 public interface TelemetryPingStore extends Parcelable {
 
     /**
-     * @return a list of all the telemetry pings in the store that are ready for upload.
+     * @return a list of all the telemetry pings in the store that are ready for upload, ascending oldest to newest.
      */
     List<TelemetryPing> getAllPings();
 
     /**
      * Save a ping to the store.
      *
      * @param ping the ping to store
      * @throws IOException for underlying store access errors

--- a/mobile/android/tests/background/junit4/src/org/mozilla/gecko/telemetry/stores/TestTelemetryJSONFilePingStore.java
+++ b/mobile/android/tests/background/junit4/src/org/mozilla/gecko/telemetry/stores/TestTelemetryJSONFilePingStore.java
@@ -15,16 +15,17 @@ import org.junit.runner.RunWith;
 import org.mozilla.gecko.background.testhelpers.TestRunner;
 import org.mozilla.gecko.sync.ExtendedJSONObject;
 import org.mozilla.gecko.telemetry.TelemetryPing;
 import org.mozilla.gecko.util.FileUtils;
 
 import java.io.File;
 import java.io.FileOutputStream;
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Set;
 import java.util.UUID;
 
 import static org.junit.Assert.*;
 
 /**
@@ -104,27 +105,40 @@ public class TestTelemetryJSONFilePingSt
         try {
             assertNotNull("File lock is released after store write", stream.getChannel().tryLock());
         } finally {
             stream.close(); // releases lock
         }
     }
 
     @Test
-    public void testGetAllPings() throws Exception {
+    public void testGetAllPingsSavesData() throws Exception {
         final String urlPrefix = "url";
         writeTestPingsToStore(3, urlPrefix);
 
         final ArrayList<TelemetryPing> pings = testStore.getAllPings();
         for (final TelemetryPing ping : pings) {
             assertEquals("Expected url path value received", urlPrefix + ping.getDocID(), ping.getURLPath());
             assertIsGeneratedPayload(ping.getPayload());
         }
     }
 
+    @Test
+    public void testGetAllPingsIsSorted() throws Exception {
+        final List<String> storedDocIDs = writeTestPingsToStore(3, "urlPrefix");
+
+        final ArrayList<TelemetryPing> pings = testStore.getAllPings();
+        for (int i = 0; i < pings.size(); ++i) {
+            final String expectedDocID = storedDocIDs.get(i);
+            final TelemetryPing ping = pings.get(i);
+
+            assertEquals("Stored ping " + i + " retrieved in order", expectedDocID, ping.getDocID());
+        }
+    }
+
     @Test // regression test: bug 1272817
     public void testGetAllPingsHandlesEmptyFiles() throws Exception {
         final int expectedPingCount = 3;
         writeTestPingsToStore(expectedPingCount, "whatever");
         assertTrue("Empty file is created", testStore.getPingFile(getDocID()).createNewFile());
         assertEquals("Returned pings only contains valid files", expectedPingCount, testStore.getAllPings().size());
     }
 
@@ -140,18 +154,17 @@ public class TestTelemetryJSONFilePingSt
     @Test
     public void testMaybePrunePingsPrunesIfAboveMax() throws Exception {
         final int pingCount = TelemetryJSONFilePingStore.MAX_PING_COUNT + 1;
         final List<String> expectedDocIDs = writeTestPingsToStore(pingCount, "whatever");
         assertStoreFileCount(pingCount);
         testStore.maybePrunePings();
         assertStoreFileCount(TelemetryJSONFilePingStore.MAX_PING_COUNT);
 
-        final HashSet<String> existingIDs = new HashSet<>(TelemetryJSONFilePingStore.MAX_PING_COUNT);
-        Collections.addAll(existingIDs, testDir.list());
+        final HashSet<String> existingIDs = new HashSet<>(Arrays.asList(testDir.list()));
         assertFalse("Oldest ping was removed", existingIDs.contains(expectedDocIDs.get(0)));
     }
 
     @Test
     public void testOnUploadAttemptCompleted() throws Exception {
         final List<String> savedDocIDs = writeTestPingsToStore(10, "url");
         final int halfSize = savedDocIDs.size() / 2;
         final Set<String> unuploadedPingIDs = new HashSet<>(savedDocIDs.subList(0, halfSize));