--- a/toolkit/components/telemetry/Histograms.json
+++ b/toolkit/components/telemetry/Histograms.json
@@ -4042,16 +4042,25 @@
     "alert_emails": ["safebrowsing-telemetry@mozilla.org"],
     "bug_numbers": [1334616],
     "expires_in_version": "never",
     "kind": "exponential",
     "high": 60000,
     "n_buckets": 30,
     "description": "Time spent inside ClassifyLocalWithTables (ms)"
   },
+  "URLCLASSIFIER_ASYNC_CLASSIFYLOCAL_TIME": {
+    "alert_emails": ["safebrowsing-telemetry@mozilla.org"],
+    "bug_numbers": [1341506],
+    "expires_in_version": "never",
+    "kind": "exponential",
+    "high": 60000,
+    "n_buckets": 30,
+    "description": "Time spent per AsyncClassifyLocalWithTables (ms)"
+  },
   "URLCLASSIFIER_PS_FILELOAD_TIME": {
     "alert_emails": ["safebrowsing-telemetry@mozilla.org"],
     "expires_in_version": "never",
     "kind": "exponential",
     "high": 1000,
     "n_buckets": 10,
     "description": "Time spent loading PrefixSet from file (ms)"
   },

--- a/toolkit/components/url-classifier/nsUrlClassifierDBService.cpp
+++ b/toolkit/components/url-classifier/nsUrlClassifierDBService.cpp
@@ -1686,16 +1686,19 @@ nsUrlClassifierDBService::AsyncClassifyL
     // TODO: e10s support. Bug 1343425.
     return NS_ERROR_NOT_IMPLEMENTED;
   }
 
   if (gShuttingDownThread) {
     return NS_ERROR_ABORT;
   }
 
+  using namespace mozilla::Telemetry;
+  auto startTime = TimeStamp::Now(); // For telemetry.
+
   nsCOMPtr<nsIURI> uri = NS_GetInnermostURI(aURI);
   NS_ENSURE_TRUE(uri, NS_ERROR_FAILURE);
 
   nsAutoCString key;
   // Canonicalize the url
   nsCOMPtr<nsIUrlClassifierUtils> utilsService =
     do_GetService(NS_URLCLASSIFIERUTILS_CONTRACTID);
   nsresult rv = utilsService->GetKeyForURI(uri, key);
@@ -1704,34 +1707,38 @@ nsUrlClassifierDBService::AsyncClassifyL
   auto worker = mWorker;
   nsCString tables(aTables);
 
   // Since aCallback will be passed around threads...
   nsMainThreadPtrHandle<nsIURIClassifierCallback> callback(
     new nsMainThreadPtrHolder<nsIURIClassifierCallback>(aCallback));
 
   nsCOMPtr<nsIRunnable> r =
-    NS_NewRunnableFunction([worker, key, tables, callback] () -> void {
+    NS_NewRunnableFunction([worker, key, tables, callback, startTime] () -> void {
 
     nsCString matchedLists;
     nsAutoPtr<LookupResultArray> results(new LookupResultArray());
     if (results) {
       nsresult rv = worker->DoLocalLookup(key, tables, results);
       if (NS_SUCCEEDED(rv)) {
         for (uint32_t i = 0; i < results->Length(); i++) {
           if (i > 0) {
             matchedLists.AppendLiteral(",");
           }
           matchedLists.Append(results->ElementAt(i).mTableName);
         }
       }
     }
 
     nsCOMPtr<nsIRunnable> cbRunnable =
-      NS_NewRunnableFunction([callback, matchedLists] () -> void {
+      NS_NewRunnableFunction([callback, matchedLists, startTime] () -> void {
+        // Measure the time diff between calling and callback.
+        AccumulateDelta_impl<Millisecond>::compute(
+          Telemetry::URLCLASSIFIER_ASYNC_CLASSIFYLOCAL_TIME, startTime);
+
         // |callback| is captured as const value so ...
         auto cb = const_cast<nsIURIClassifierCallback*>(callback.get());
         cb->OnClassifyComplete(NS_OK,           // Not used.
                                matchedLists,
                                EmptyCString(),  // provider. (Not used)
                                EmptyCString()); // prefix. (Not used)
       });