new file mode 100644
--- /dev/null
+++ b/mobile/android/base/java/org/mozilla/gecko/telemetry/TelemetryPingFromStore.java
@@ -0,0 +1,24 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+package org.mozilla.gecko.telemetry;
+
+import org.mozilla.gecko.sync.ExtendedJSONObject;
+import org.mozilla.gecko.telemetry.stores.TelemetryPingStore;
+
+/**
+ * Container for telemetry data and the data necessary to upload it, as
+ * returned by a {@link TelemetryPingStore}.
+ */
+public class TelemetryPingFromStore extends TelemetryPing {
+    private final int uniqueID;
+
+    public TelemetryPingFromStore(final String url, final ExtendedJSONObject payload, final int uniqueID) {
+        super(url, payload);
+        this.uniqueID = uniqueID;
+    }
+
+    public int getUniqueID() { return uniqueID; }
+}
+

new file mode 100644
--- /dev/null
+++ b/mobile/android/base/java/org/mozilla/gecko/telemetry/schedulers/TelemetryUploadScheduler.java
@@ -0,0 +1,26 @@
+/*
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, you can obtain one at http://mozilla.org/MPL/2.0/.
+ */
+
+package org.mozilla.gecko.telemetry.schedulers;
+
+import android.content.Context;
+import org.mozilla.gecko.telemetry.stores.TelemetryPingStore;
+
+/**
+ * An implementation of this class can investigate the given {@link TelemetryPingStore} to
+ * decide if it's ready to upload the pings inside that Store (e.g. on wifi? have we
+ * accumulated X pings?) and can schedule that upload. Typically, the upload will be
+ * scheduled by sending an {@link android.content.Intent} to the
+ * {@link org.mozilla.gecko.telemetry.TelemetryUploadService}, either immediately or
+ * via an external scheduler (e.g. {@link android.app.job.JobScheduler}).
+ *
+ * N.B.: If the Store is not ready to upload, an implementation *should not* try to reschedule
+ * the check to see if it's time to upload - this is expected to be handled by the caller.
+ */
+public interface TelemetryUploadScheduler {
+    boolean isReadyToUpload(TelemetryPingStore store);
+    void scheduleUpload(Context context, TelemetryPingStore store);
+}

new file mode 100644
--- /dev/null
+++ b/mobile/android/base/java/org/mozilla/gecko/telemetry/stores/TelemetryPingStore.java
@@ -0,0 +1,51 @@
+/*
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, you can obtain one at http://mozilla.org/MPL/2.0/.
+ */
+
+package org.mozilla.gecko.telemetry.stores;
+
+import android.os.Parcelable;
+import org.mozilla.gecko.telemetry.TelemetryPing;
+import org.mozilla.gecko.telemetry.TelemetryPingFromStore;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Set;
+
+/**
+ * Persistent storage for TelemetryPings that are queued for upload.
+ *
+ * An implementation of this class is expected to be thread-safe.
+ */
+public interface TelemetryPingStore extends Parcelable {
+
+    /**
+     * @return a list of all the telemetry pings in the store that are ready for upload.
+     */
+    ArrayList<TelemetryPingFromStore> getAllPings();
+
+    /**
+     * Save a ping to the store.
+     *
+     * @param uniqueID a unique identifier for the ping - will be returned in {@link #onUploadAttemptComplete(Set)}
+     * @param ping the ping to store
+     * @throws IOException for underlying store access errors
+     */
+    void storePing(long uniqueID, TelemetryPing ping) throws IOException;
+
+    /**
+     * Removes telemetry pings from the store if there are too many pings or they take up too much space.
+     */
+    void maybePrunePings();
+
+    /**
+     * Removes the successfully uploaded pings from the database and performs another other actions necessary
+     * for when upload is completed.
+     *
+     * @param successfulRemoveIDs unique ids of pings passed to {@link #storePing(long, TelemetryPing)} that were
+     *                            successfully uploaded
+     */
+    void onUploadAttemptComplete(Set<Integer> successfulRemoveIDs);
+}

--- a/mobile/android/base/moz.build
+++ b/mobile/android/base/moz.build
@@ -567,19 +567,22 @@ gbjar.sources += ['java/org/mozilla/geck
     'tabs/TabsGridLayout.java',
     'tabs/TabsLayoutAdapter.java',
     'tabs/TabsLayoutItemView.java',
     'tabs/TabsListLayout.java',
     'tabs/TabsPanel.java',
     'tabs/TabsPanelThumbnailView.java',
     'Telemetry.java',
     'telemetry/core/TelemetryCorePingBuilder.java',
+    'telemetry/schedulers/TelemetryUploadScheduler.java',
+    'telemetry/stores/TelemetryPingStore.java',
     'telemetry/TelemetryConstants.java',
     'telemetry/TelemetryPing.java',
     'telemetry/TelemetryPingBuilder.java',
+    'telemetry/TelemetryPingFromStore.java',
     'telemetry/TelemetryUploadService.java',
     'TelemetryContract.java',
     'text/FloatingActionModeCallback.java',
     'text/FloatingToolbarTextSelection.java',
     'text/TextAction.java',
     'text/TextSelection.java',
     'TextSelectionHandle.java',
     'ThumbnailHelper.java',