--- a/mobile/android/base/java/org/mozilla/gecko/telemetry/stores/TelemetryPingStore.java
+++ b/mobile/android/base/java/org/mozilla/gecko/telemetry/stores/TelemetryPingStore.java
@@ -32,16 +32,17 @@ public interface TelemetryPingStore exte
      *
      * @param ping the ping to store
      * @throws IOException for underlying store access errors
      */
     void storePing(TelemetryPing ping) throws IOException;
 
     /**
      * Removes telemetry pings from the store if there are too many pings or they take up too much space.
+     * Pings should be removed from oldest to newest.
      */
     void maybePrunePings();
 
     /**
      * Removes the successfully uploaded pings from the database and performs another other actions necessary
      * for when upload is completed.
      *
      * @param successfulRemoveIDs doc ids of pings that were successfully uploaded

--- 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
@@ -135,26 +135,24 @@ public class TestTelemetryJSONFilePingSt
         assertStoreFileCount(pingCount);
         testStore.maybePrunePings();
         assertStoreFileCount(pingCount);
     }
 
     @Test
     public void testMaybePrunePingsPrunesIfAboveMax() throws Exception {
         final int pingCount = TelemetryJSONFilePingStore.MAX_PING_COUNT + 1;
-        writeTestPingsToStore(pingCount, "whatever");
+        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);
-        for (final String filename : testDir.list()) {
-            existingIDs.add(filename);
-        }
-        assertFalse("Smallest ID was removed", existingIDs.contains(1));
+        Collections.addAll(existingIDs, 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));
         final Set<String> removedPingIDs = new HashSet<>(savedDocIDs.subList(halfSize, savedDocIDs.size()));
@@ -179,26 +177,32 @@ public class TestTelemetryJSONFilePingSt
      * Writes pings to store without using store API with:
      *   server = urlPrefix + docID
      *   payload = generated payload
      *
      * The docID is stored as the filename.
      *
      * Note: assumes {@link TelemetryJSONFilePingStore#getPingFile(String)} works.
      *
-     * @return a list of doc IDs saved to disk
+     * @return a list of doc IDs saved to disk in ascending order of last modified date
      */
     private List<String> writeTestPingsToStore(final int count, final String urlPrefix) throws Exception {
         final List<String> savedDocIDs = new ArrayList<>(count);
+        final long now = System.currentTimeMillis();
         for (int i = 1; i <= count; ++i) {
             final String docID = getDocID();
             final JSONObject obj = new JSONObject()
                     .put(TelemetryJSONFilePingStore.KEY_URL_PATH, urlPrefix + docID)
                     .put(TelemetryJSONFilePingStore.KEY_PAYLOAD, generateTelemetryPayload());
-            FileUtils.writeJSONObjectToFile(testStore.getPingFile(docID), obj);
+            final File pingFile = testStore.getPingFile(docID);
+            FileUtils.writeJSONObjectToFile(pingFile, obj);
+
+            // If we don't set an explicit time, the modified times are all equal.
+            // Also, last modified times are rounded by second.
+            assertTrue("Able to set last modified time", pingFile.setLastModified(now - (count * 10_000) + i * 10_000));
             savedDocIDs.add(docID);
         }
         return savedDocIDs;
     }
 
     private String getDocID() {
         return UUID.randomUUID().toString();
     }