--- a/mobile/android/base/java/org/mozilla/gecko/telemetry/TelemetryUploadService.java
+++ b/mobile/android/base/java/org/mozilla/gecko/telemetry/TelemetryUploadService.java
@@ -4,32 +4,37 @@
 
 package org.mozilla.gecko.telemetry;
 
 import android.app.IntentService;
 import android.content.Context;
 import android.content.Intent;
 import android.content.SharedPreferences;
 import android.util.Log;
+import ch.boye.httpclientandroidlib.HttpHeaders;
 import ch.boye.httpclientandroidlib.HttpResponse;
 import ch.boye.httpclientandroidlib.client.ClientProtocolException;
+import ch.boye.httpclientandroidlib.client.methods.HttpRequestBase;
+import ch.boye.httpclientandroidlib.impl.client.DefaultHttpClient;
 import org.mozilla.gecko.GeckoProfile;
 import org.mozilla.gecko.GeckoSharedPrefs;
 import org.mozilla.gecko.preferences.GeckoPreferences;
 import org.mozilla.gecko.sync.ExtendedJSONObject;
 import org.mozilla.gecko.sync.net.BaseResource;
 import org.mozilla.gecko.sync.net.BaseResourceDelegate;
 import org.mozilla.gecko.sync.net.Resource;
 import org.mozilla.gecko.telemetry.stores.TelemetryPingStore;
+import org.mozilla.gecko.util.DateUtil;
 import org.mozilla.gecko.util.NetworkUtils;
 import org.mozilla.gecko.util.StringUtils;
 
 import java.io.IOException;
 import java.net.URISyntaxException;
 import java.security.GeneralSecurityException;
+import java.util.Calendar;
 import java.util.HashSet;
 import java.util.List;
 import java.util.concurrent.TimeUnit;
 
 /**
  * The service that handles retrieving a list of telemetry pings to upload from the given
  * {@link TelemetryPingStore}, uploading those payloads to the associated server, and reporting
  * back to the Store which uploads were a success.
@@ -295,16 +300,22 @@ public class TelemetryUploadService exte
             // We don't log the exception to prevent leaking user data.
             Log.w(LOGTAG, "Transport exception when trying to upload telemetry");
             hadConnectionError = true;
         }
 
         private boolean hadConnectionError() {
             return hadConnectionError;
         }
+
+        @Override
+        public void addHeaders(final HttpRequestBase request, final DefaultHttpClient client) {
+            super.addHeaders(request, client);
+            request.addHeader(HttpHeaders.DATE, DateUtil.getDateInHTTPFormat(Calendar.getInstance().getTime()));
+        }
     }
 
     /**
      * A hack because I want to set the resource after the Delegate is constructed.
      * Be sure to call {@link #setResource(Resource)}!
      */
     private static abstract class ResultDelegate extends BaseResourceDelegate {
         public ResultDelegate() {

new file mode 100644
--- /dev/null
+++ b/mobile/android/base/java/org/mozilla/gecko/util/DateUtil.java
@@ -0,0 +1,30 @@
+/*
+ * 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.util;
+
+import java.text.DateFormat;
+import java.text.SimpleDateFormat;
+import java.util.Date;
+import java.util.Locale;
+import java.util.TimeZone;
+
+/**
+ * Utilities to help with manipulating Java's dates and calendars.
+ */
+public class DateUtil {
+    private DateUtil() {}
+
+    /**
+     * @param date the date to convert to HTTP format
+     * @return the date as specified in rfc 1123, e.g. "Tue, 01 Feb 2011 14:00:00 GMT"
+     */
+    public static String getDateInHTTPFormat(final Date date) {
+        final DateFormat df = new SimpleDateFormat("E, dd MMM yyyy HH:mm:ss z", Locale.US);
+        df.setTimeZone(TimeZone.getTimeZone("GMT"));
+        return df.format(date);
+    }
+}

--- a/mobile/android/base/moz.build
+++ b/mobile/android/base/moz.build
@@ -92,16 +92,17 @@ mgjar.javac_flags += ['-Xlint:all']
 gujar = add_java_jar('gecko-util')
 gujar.sources += ['java/org/mozilla/gecko/' + x for x in [
     'util/ActivityResultHandler.java',
     'util/ActivityResultHandlerMap.java',
     'util/ActivityUtils.java',
     'util/BundleEventListener.java',
     'util/Clipboard.java',
     'util/ContextUtils.java',
+    'util/DateUtil.java',
     'util/DrawableUtil.java',
     'util/EventCallback.java',
     'util/FileUtils.java',
     'util/FloatUtils.java',
     'util/GamepadUtils.java',
     'util/GeckoBackgroundThread.java',
     'util/GeckoEventListener.java',
     'util/GeckoJarReader.java',

new file mode 100644
--- /dev/null
+++ b/mobile/android/tests/background/junit4/src/org/mozilla/gecko/util/TestDateUtil.java
@@ -0,0 +1,35 @@
+/*
+ * 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.util;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.mozilla.gecko.background.testhelpers.TestRunner;
+
+import java.util.Calendar;
+import java.util.GregorianCalendar;
+import java.util.Locale;
+import java.util.TimeZone;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * Unit tests for date utilities.
+ */
+@RunWith(TestRunner.class)
+public class TestDateUtil {
+    @Test
+    public void testGetDateInHTTPFormat() {
+        final TimeZone gmt = TimeZone.getTimeZone("GMT");
+        final GregorianCalendar calendar = new GregorianCalendar(gmt, Locale.US);
+        calendar.set(2011, Calendar.FEBRUARY, 1, 14, 0, 0);
+        final String expectedDate = "Tue, 01 Feb 2011 14:00:00 GMT";
+
+        final String actualDate = DateUtil.getDateInHTTPFormat(calendar.getTime());
+        assertEquals("Returned date is expected", expectedDate, actualDate);
+    }
+}