--- a/browser/components/extensions/ext-history.js
+++ b/browser/components/extensions/ext-history.js
@@ -4,16 +4,53 @@
 
 const {classes: Cc, interfaces: Ci, utils: Cu} = Components;
 
 XPCOMUtils.defineLazyGetter(this, "History", () => {
   Cu.import("resource://gre/modules/PlacesUtils.jsm");
   return PlacesUtils.history;
 });
 
+Cu.import("resource://gre/modules/ExtensionUtils.jsm");
+const {
+  normalizeTime,
+} = ExtensionUtils;
+
+
+/*
+ * Converts a nsINavHistoryContainerResultNode into an array of objects
+ *
+ * https://developer.mozilla.org/en-US/docs/XPCOM_Interface_Reference/nsINavHistoryContainerResultNode
+ */
+function convertNavHistoryContainerResultNode(container) {
+  let results = [];
+  container.containerOpen = true;
+  for (let i = 0; i < container.childCount; i++) {
+    let node = container.getChild(i);
+    results.push(convertNavHistoryResultNode(node));
+  }
+  container.containerOpen = false;
+  return results;
+}
+
+/*
+ * Converts a nsINavHistoryResultNode into a plain object
+ *
+ * https://developer.mozilla.org/en-US/docs/XPCOM_Interface_Reference/nsINavHistoryResultNode
+ */
+function convertNavHistoryResultNode(node) {
+  return {
+    id: node.pageGuid,
+    url: node.uri,
+    title: node.title,
+    lastVisitTime: PlacesUtils.toTime(node.time),
+    visitCount: node.accessCount,
+  };
+}
+
 extensions.registerSchemaAPI("history", "history", (extension, context) => {
   return {
     history: {
       deleteAll: function() {
         return History.clear();
       },
       deleteRange: function(filter) {
         let newFilter = {
@@ -23,11 +60,32 @@ extensions.registerSchemaAPI("history", 
         // History.removeVisitsByFilter returns a boolean, but our API should return nothing
         return History.removeVisitsByFilter(newFilter).then(() => undefined);
       },
       deleteUrl: function(details) {
         let url = details.url;
         // History.remove returns a boolean, but our API should return nothing
         return History.remove(url).then(() => undefined);
       },
+      search: function(query) {
+        let beginTime = (query.startTime == null) ?
+                          PlacesUtils.toPRTime(Date.now() -  24 * 60 * 60 * 1000) :
+                          PlacesUtils.toPRTime(normalizeTime(query.startTime));
+        let endTime = PlacesUtils.toPRTime(normalizeTime(query.endTime, false));
+        if (beginTime > endTime) {
+          return Promise.reject({message: "The startTime cannot be after the endTime"});
+        }
+
+        let options = History.getNewQueryOptions();
+        options.sortingMode = options.SORT_BY_DATE_DESCENDING;
+        options.maxResults = query.maxResults || 100;
+
+        let historyQuery = History.getNewQuery();
+        historyQuery.searchTerms = query.text;
+        historyQuery.beginTime = beginTime;
+        historyQuery.endTime = endTime;
+        let queryResult = History.executeQuery(historyQuery, options).root;
+        let results = convertNavHistoryContainerResultNode(queryResult);
+        return Promise.resolve(results);
+      },
     },
   };
 });

--- a/browser/components/extensions/schemas/history.json
+++ b/browser/components/extensions/schemas/history.json
@@ -85,48 +85,60 @@
             "type": "string",
             "description": "The visit ID of the referrer."
           },
           "transition": {
             "$ref": "TransitionType",
             "description": "The $(topic:transition-types)[transition type] for this visit from its referrer."
           }
         }
+      },
+      {
+        "id": "HistoryTime",
+        "description": "A time specified as a Date object, a number or string representing milliseconds since the epoch, or an ISO 8601 string",
+        "choices": [
+          {
+            "type": "string",
+            "pattern": "^[1-9]\\d*$"
+          },
+          {
+            "$ref": "extensionTypes.Date"
+          }
+        ]
       }
     ],
     "functions": [
       {
         "name": "search",
-        "unsupported": true,
         "type": "function",
         "description": "Searches the history for the last visit time of each page matching the query.",
         "async": "callback",
         "parameters": [
           {
             "name": "query",
             "type": "object",
             "properties": {
               "text": {
                 "type": "string",
                 "description": "A free-text query to the history service.  Leave empty to retrieve all pages."
               },
               "startTime": {
-                "type": "number",
+                "$ref": "HistoryTime",
                 "optional": true,
-                "description": "Limit results to those visited after this date, represented in milliseconds since the epoch. If not specified, this defaults to 24 hours in the past."
+                "description": "Limit results to those visited after this date. If not specified, this defaults to 24 hours in the past."
               },
               "endTime": {
-                "type": "number",
+                "$ref": "HistoryTime",
                 "optional": true,
-                "description": "Limit results to those visited before this date, represented in milliseconds since the epoch."
+                "description": "Limit results to those visited before this date."
               },
               "maxResults": {
                 "type": "integer",
                 "optional": true,
-                "minimum": 0,
+                "minimum": 1,
                 "description": "The maximum number of results to retrieve.  Defaults to 100."
               }
             }
           },
           {
             "name": "callback",
             "type": "function",
             "parameters": [

--- a/browser/components/extensions/test/browser/browser_ext_history.js
+++ b/browser/components/extensions/test/browser/browser_ext_history.js
@@ -44,17 +44,17 @@ add_task(function* test_delete() {
   yield extension.awaitMessage("ready");
 
   let visits = [];
 
   // Add 5 visits for one uri and 3 visits for 3 others
   for (let i = 0; i < 8; ++i) {
     let baseUri = "http://mozilla.com/test_history/";
     let uri = (i > 4) ? `${baseUri}${i}/` : baseUri;
-    let dbDate = (Number(REFERENCE_DATE) + 3600 * 1000 * i) * 1000;
+    let dbDate = PlacesUtils.toPRTime(Number(REFERENCE_DATE) + 3600 * 1000 * i);
 
     let visit = {
       uri,
       title: "visit " + i,
       visitDate: dbDate,
     };
     visits.push(visit);
   }
@@ -66,30 +66,30 @@ add_task(function* test_delete() {
   let testUrl = visits[6].uri.spec;
   ok(yield PlacesTestUtils.isPageInDB(testUrl), "expected url found in history database");
 
   extension.sendMessage("delete-url", testUrl);
   yield extension.awaitMessage("url-deleted");
   is(yield PlacesTestUtils.isPageInDB(testUrl), false, "expected url not found in history database");
 
   let filter = {
-    startTime: visits[1].visitDate / 1000,
-    endTime: visits[3].visitDate / 1000,
+    startTime: PlacesUtils.toTime(visits[1].visitDate),
+    endTime: PlacesUtils.toTime(visits[3].visitDate),
   };
 
   extension.sendMessage("delete-range", filter);
   yield extension.awaitMessage("range-deleted");
 
   ok(yield PlacesTestUtils.isPageInDB(visits[0].uri), "expected uri found in history database");
   is(yield PlacesTestUtils.visitsInDB(visits[0].uri), 2, "2 visits for uri found in history database");
   ok(yield PlacesTestUtils.isPageInDB(visits[5].uri), "expected uri found in history database");
   is(yield PlacesTestUtils.visitsInDB(visits[5].uri), 1, "1 visit for uri found in history database");
 
-  filter.startTime = visits[0].visitDate / 1000;
-  filter.endTime = visits[5].visitDate / 1000;
+  filter.startTime = PlacesUtils.toTime(visits[0].visitDate);
+  filter.endTime = PlacesUtils.toTime(visits[5].visitDate);
 
   extension.sendMessage("delete-range", filter);
   yield extension.awaitMessage("range-deleted");
 
   is(yield PlacesTestUtils.isPageInDB(visits[0].uri), false, "expected uri not found in history database");
   is(yield PlacesTestUtils.visitsInDB(visits[0].uri), 0, "0 visits for uri found in history database");
   is(yield PlacesTestUtils.isPageInDB(visits[5].uri), false, "expected uri not found in history database");
   is(yield PlacesTestUtils.visitsInDB(visits[5].uri), 0, "0 visits for uri found in history database");
@@ -97,8 +97,96 @@ add_task(function* test_delete() {
   ok(yield PlacesTestUtils.isPageInDB(visits[7].uri), "expected uri found in history database");
 
   extension.sendMessage("delete-all");
   yield extension.awaitMessage("urls-deleted");
   is(PlacesUtils.history.hasHistoryEntries, false, "history is empty");
 
   yield extension.unload();
 });
+
+add_task(function* test_search() {
+  const SINGLE_VISIT_URL = "http://example.com/";
+  const DOUBLE_VISIT_URL = "http://example.com/2/";
+  const MOZILLA_VISIT_URL = "http://mozilla.com/";
+
+  function background() {
+    browser.test.onMessage.addListener(msg => {
+      browser.history.search({text: ""}).then(results => {
+        browser.test.sendMessage("empty-search", results);
+        return browser.history.search({text: "mozilla.com"});
+      }).then(results => {
+        browser.test.sendMessage("text-search", results);
+        return browser.history.search({text: "example.com", maxResults: 1});
+      }).then(results => {
+        browser.test.sendMessage("max-results-search", results);
+        return browser.history.search({text: "", startTime: Date.now()});
+      }).then(results => {
+        browser.test.assertEq(0, results.length, "no results returned for late start time");
+        return browser.history.search({text: "", endTime: 0});
+      }).then(results => {
+        browser.test.assertEq(0, results.length, "no results returned for early end time");
+        return browser.history.search({text: "", startTime: Date.now(), endTime: 0});
+      }).then(results =>
+        {
+          browser.test.fail("history.search rejects with startTime that is after the endTime");
+        }, error => {
+          browser.test.assertEq(
+            error.message,
+            "The startTime cannot be after the endTime",
+            "history.search rejects with startTime that is after the endTime");
+      }).then(() => {
+        browser.test.notifyPass("search");
+      });
+    });
+
+    browser.test.sendMessage("ready");
+  }
+
+  let extension = ExtensionTestUtils.loadExtension({
+    manifest: {
+      permissions: ["history"],
+    },
+    background: `(${background})()`,
+  });
+
+  function findResult(url, results) {
+    return results.find(r => r.url === url);
+  }
+
+  function checkResult(results, url, expectedCount) {
+    let result = findResult(url, results);
+    isnot(result, null, `history.search result was found for ${url}`);
+    is(result.visitCount, expectedCount, `history.search reports ${expectedCount} visit(s)`);
+    is(result.title, `test visit for ${url}`, "title for search result is correct");
+  }
+
+  yield extension.startup();
+  yield extension.awaitMessage("ready");
+  yield PlacesTestUtils.clearHistory();
+
+  yield PlacesTestUtils.addVisits([
+    { uri: makeURI(MOZILLA_VISIT_URL) },
+    { uri: makeURI(DOUBLE_VISIT_URL) },
+    { uri: makeURI(SINGLE_VISIT_URL) },
+    { uri: makeURI(DOUBLE_VISIT_URL) },
+  ]);
+
+  extension.sendMessage("check-history");
+
+  let results = yield extension.awaitMessage("empty-search");
+  is(results.length, 3, "history.search returned 3 results");
+  checkResult(results, SINGLE_VISIT_URL, 1);
+  checkResult(results, DOUBLE_VISIT_URL, 2);
+  checkResult(results, MOZILLA_VISIT_URL, 1);
+
+  results = yield extension.awaitMessage("text-search");
+  is(results.length, 1, "history.search returned 1 result");
+  checkResult(results, MOZILLA_VISIT_URL, 1);
+
+  results = yield extension.awaitMessage("max-results-search");
+  is(results.length, 1, "history.search returned 1 result");
+  checkResult(results, DOUBLE_VISIT_URL, 2);
+
+  yield extension.awaitFinish("search");
+  yield extension.unload();
+  yield PlacesTestUtils.clearHistory();
+});

--- a/toolkit/components/places/PlacesUtils.jsm
+++ b/toolkit/components/places/PlacesUtils.jsm
@@ -256,16 +256,39 @@ this.PlacesUtils = {
    *          The string spec of the URI
    * @returns A URI object for the spec.
    */
   _uri: function PU__uri(aSpec) {
     return NetUtil.newURI(aSpec);
   },
 
   /**
+   * Convert a Date object to a PRTime (microseconds).
+   *
+   * @param date
+   *        the Date object to convert.
+   * @return microseconds from the epoch.
+   */
+  toPRTime: function PU_toPRTime(date) {
+    return date * 1000;
+  },
+
+  /**
+   * Convert a PRTime to a time.
+   *
+   * @param time
+   *        microseconds from the epoch.
+   * @return time
+   *        milliseconds from the epoch.
+   */
+  toTime: function PU_toTime(time) {
+    return time / 1000;
+  },
+
+  /**
    * Wraps a string in a nsISupportsString wrapper.
    * @param   aString
    *          The string to wrap.
    * @returns A nsISupportsString object containing a string.
    */
   toISupportsString: function PU_toISupportsString(aString) {
     let s = Cc["@mozilla.org/supports-string;1"].
             createInstance(Ci.nsISupportsString);