--- a/toolkit/components/extensions/ext-downloads.js
+++ b/toolkit/components/extensions/ext-downloads.js
@@ -190,17 +190,24 @@ function downloadQuery(query) {
       }
     }
   }
 
   function normalizeTime(arg, before) {
     if (arg == null) {
       return before ? Number.MAX_VALUE : 0;
     }
-    return parseInt(arg, 10);
+
+    // We accept several formats: a Date object, an ISO8601 string, or a
+    // number of milliseconds since the epoch as either a number or a string.
+    // The "number of milliseconds since the epoch as a string" is an outlier,
+    // everything else can just be passed directly to the Date constructor.
+    const date = new Date((typeof arg == "string" && /^\d+$/.test(arg))
+                          ? parseInt(arg, 10) : arg);
+    return date.valueOf();
   }
 
   const startedBefore = normalizeTime(query.startedBefore, true);
   const startedAfter = normalizeTime(query.startedAfter, false);
   // const endedBefore = normalizeTime(query.endedBefore, true);
   // const endedAfter = normalizeTime(query.endedAfter, false);
 
   const totalBytesGreater = query.totalBytesGreater || 0;

--- a/toolkit/components/extensions/schemas/downloads.json
+++ b/toolkit/components/extensions/schemas/downloads.json
@@ -203,16 +203,29 @@
             "optional": true,
             "type": "boolean"
           },
           "previous": {
             "optional": true,
             "type": "boolean"
           }
         }
+      },
+      {
+        "id": "DownloadTime",
+        "description": "A time specified as a Date object, a number of string representing milliseconds since the epoch, or an ISO 8601 string",
+        "choices": [
+          {
+            "type": "string",
+            "pattern": "^[1-9]\\d*$"
+          },
+          {
+            "$ref": "extensionTypes.Date"
+          }
+        ]
       }
     ],
     "functions": [
       {
         "name": "download",
         "type": "function",
         "async": "callback",
         "description": "Download a URL. If the URL uses the HTTP[S] protocol, then the request will include all cookies currently set for its hostname. If both <code>filename</code> and <code>saveAs</code> are specified, then the Save As dialog will be displayed, pre-populated with the specified <code>filename</code>. If the download started successfully, <code>callback</code> will be called with the new <a href='#type-DownloadItem'>DownloadItem</a>'s <code>downloadId</code>. If there was an error starting the download, then <code>callback</code> will be called with <code>downloadId=undefined</code> and <a href='extension.html#property-lastError'>chrome.extension.lastError</a> will contain a descriptive string. The error strings are not guaranteed to remain backwards compatible between releases. You must not parse it.",
@@ -306,36 +319,32 @@
                 "description": "This array of search terms limits results to <a href='#type-DownloadItem'>DownloadItems</a> whose <code>filename</code> or <code>url</code> contain all of the search terms that do not begin with a dash '-' and none of the search terms that do begin with a dash.",
                 "optional": true,
                 "type": "array",
                 "items": { "type": "string" }
               },
               "startedBefore": {
                 "description": "Limits results to downloads that started before the given ms since the epoch.",
                 "optional": true,
-                "type": "string",
-                "pattern": "^[1-9]\\d*$"
+                "$ref": "DownloadTime"
               },
               "startedAfter": {
                 "description": "Limits results to downloads that started after the given ms since the epoch.",
                 "optional": true,
-                "type": "string",
-                "pattern": "^[1-9]\\d*$"
+                "$ref": "DownloadTime"
               },
               "endedBefore": {
                 "description": "Limits results to downloads that ended before the given ms since the epoch.",
                 "optional": true,
-                "type": "string",
-                "pattern": "^[1-9]\\d*$"
+                "$ref": "DownloadTime"
               },
               "endedAfter": {
                 "description": "Limits results to downloads that ended after the given ms since the epoch.",
                 "optional": true,
-                "type": "string",
-                "pattern": "^[1-9]\\d*$"
+                "$ref": "DownloadTime"
               },
               "totalBytesGreater": {
                 "description": "Limits results to downloads whose totalBytes is greater than the given integer.",
                 "optional": true,
                 "type": "number"
               },
               "totalBytesLess": {
                 "description": "Limits results to downloads whose totalBytes is less than the given integer.",

--- a/toolkit/components/extensions/test/mochitest/test_chrome_ext_downloads_search.html
+++ b/toolkit/components/extensions/test/mochitest/test_chrome_ext_downloads_search.html
@@ -269,37 +269,52 @@ add_task(function* test_search() {
   yield checkSearch({query: ["nEwfILe"]}, ["txt2"], "term nEwfiLe");
 
   // Check that negative search terms work.
   yield checkSearch({query: ["-txt"]}, ["html1", "html2"], "term -txt");
 
   // Check that positive and negative search terms together work.
   yield checkSearch({query: ["html", "-renamed"]}, ["html1"], "postive and negative terms");
 
-  // Check that startedBefore works with stringified milliseconds.
-  yield checkSearch({startedBefore: time1.valueOf().toString()}, [], "before time1");
-  yield checkSearch({startedBefore: time2.valueOf().toString()}, ["txt1", "txt2"], "before time2");
-  yield checkSearch({startedBefore: time3.valueOf().toString()}, ["txt1", "txt2", "html1", "html2"], "before time3");
+  function* checkSearchWithDate(query, expected, description) {
+    const fields = Object.keys(query);
+    if (fields.length != 1 || !(query[fields[0]] instanceof Date)) {
+      throw new Error("checkSearchWithDate expects exactly one Date field");
+    }
+    const field = fields[0];
+    const date = query[field];
 
-  // Check that startedBefore works with iso string.
-  // enable with fix for bug 1251766
-  // yield checkSearch({startedBefore: time1.toISOString()}, [], "before time1");
-  // yield checkSearch({startedBefore: time2.toISOString()}, ["txt1", "txt2"], "before time2");
-  // yield checkSearch({startedBefore: time3.toISOString()}, ["txt1", "txt2", "html1", "html2"], "before time3");
+    let newquery = {};
+
+    // Check as a Date
+    newquery[field] = date;
+    yield checkSearch(newquery, expected, `${description} as Date`);
+
+    // Check as numeric milliseconds
+    newquery[field] = date.valueOf();
+    yield checkSearch(newquery, expected, `${description} as numeric ms`);
 
-  // Check that startedAfter works with stringified milliseconds.
-  yield checkSearch({startedAfter: time1.valueOf().toString()}, ["txt1", "txt2", "html1", "html2"], "after time1");
-  yield checkSearch({startedAfter: time2.valueOf().toString()}, ["html1", "html2"], "after time2");
-  yield checkSearch({startedAfter: time3.valueOf().toString()}, [], "after time3");
+    // Check as stringified milliseconds
+    newquery[field] = date.valueOf().toString();
+    yield checkSearch(newquery, expected, `${description} as string ms`);
+
+    // Check as ISO string
+    newquery[field] = date.toISOString();
+    yield checkSearch(newquery, expected, `${description} as iso string`);
+  }
 
-  // Check that startedAfter works with iso string.
-  // enable with fix for bug 1251766
-  // yield checkSearch({startedAfter: time1.toISOString()}, ["txt1", "txt2", "html1", "html2"], "after time1");
-  // yield checkSearch({startedAfter: time2.toISOString()}, ["html1", "html2"], "after time2");
-  // yield checkSearch({startedAfter: time3.toISOString()}, [], "after time3");
+  // Check startedBefore
+  yield checkSearchWithDate({startedBefore: time1}, [], "before time1");
+  yield checkSearchWithDate({startedBefore: time2}, ["txt1", "txt2"], "before time2");
+  yield checkSearchWithDate({startedBefore: time3}, ["txt1", "txt2", "html1", "html2"], "before time3");
+
+  // Check startedAfter
+  yield checkSearchWithDate({startedAfter: time1}, ["txt1", "txt2", "html1", "html2"], "after time1");
+  yield checkSearchWithDate({startedAfter: time2}, ["html1", "html2"], "after time2");
+  yield checkSearchWithDate({startedAfter: time3}, [], "after time3");
 
   // Check simple search on totalBytes
   yield checkSearch({totalBytes: TXT_LEN}, ["txt1", "txt2"], "totalBytes");
   yield checkSearch({totalBytes: HTML_LEN}, ["html1", "html2"], "totalBytes");
 
   // Check simple test on totalBytes{Greater,Less}
   // (NB: TXT_LEN < HTML_LEN < BIG_LEN)
   yield checkSearch({totalBytesGreater: 0}, ["txt1", "txt2", "html1", "html2"], "totalBytesGreater than 0");
@@ -370,20 +385,20 @@ add_task(function* test_search() {
     let msg = yield search(query);
     is(msg.status, "error", "search() failed");
     ok(pattern.test(msg.errmsg), `error message for ${description} was correct (${msg.errmsg}).`);
   }
 
   yield checkBadSearch("myquery", /Incorrect argument type/, "query is not an object");
   yield checkBadSearch({bogus: "boo"}, /Unexpected property/, "query contains an unknown field");
   yield checkBadSearch({query: "query string"}, /Expected array/, "query.query is a string");
-  yield checkBadSearch({startedBefore: "i am not a number"}, /Type error/, "query.startedBefore is not a valid time");
-  yield checkBadSearch({startedAfter: "i am not a number"}, /Type error/, "query.startedAfter is not a valid time");
-  yield checkBadSearch({endedBefore: "i am not a number"}, /Type error/, "query.endedBefore is not a valid time");
-  yield checkBadSearch({endedAfter: "i am not a number"}, /Type error/, "query.endedAfter is not a valid time");
+  yield checkBadSearch({startedBefore: "i am not a time"}, /Type error/, "query.startedBefore is not a valid time");
+  yield checkBadSearch({startedAfter: "i am not a time"}, /Type error/, "query.startedAfter is not a valid time");
+  yield checkBadSearch({endedBefore: "i am not a time"}, /Type error/, "query.endedBefore is not a valid time");
+  yield checkBadSearch({endedAfter: "i am not a time"}, /Type error/, "query.endedAfter is not a valid time");
   yield checkBadSearch({urlRegex: "["}, /Invalid urlRegex/, "query.urlRegexp is not a valid regular expression");
   yield checkBadSearch({filenameRegex: "["}, /Invalid filenameRegex/, "query.filenameRegexp is not a valid regular expression");
   yield checkBadSearch({orderBy: "startTime"}, /Expected array/, "query.orderBy is not an array");
   yield checkBadSearch({orderBy: ["bogus"]}, /Invalid orderBy field/, "query.orderBy references a non-existent field");
 
   yield extension.unload();
 });