--- a/toolkit/components/telemetry/Histograms.json
+++ b/toolkit/components/telemetry/Histograms.json
@@ -2039,17 +2039,17 @@
     "description": "SSL Version (1=tls1, 2=tls1.1, 3=tls1.2, 4=tls1.3)"
   },
   "SSL_HANDSHAKE_RESULT": {
     "alert_emails": ["seceng-telemetry@mozilla.com"],
     "bug_numbers": [1331280],
     "expires_in_version": "never",
     "kind": "enumerated",
     "n_values": 672,
-    "releaseChannelCollection": "opt-out",      
+    "releaseChannelCollection": "opt-out",
     "description": "SSL handshake result, 0=success, 1-255=NSS error offset, 256-511=SEC error offset + 256, 512-639=NSPR error offset + 512, 640-670=PKIX error, 671=unknown err"
   },
   "SSL_TIME_UNTIL_READY": {
     "alert_emails": ["seceng-telemetry@mozilla.com"],
     "expires_in_version": "never",
     "kind": "exponential",
     "high": 60000,
     "n_buckets": 200,
@@ -6304,24 +6304,37 @@
   },
   "TELEMETRY_TEST_KEYED_COUNT": {
     "alert_emails": ["telemetry-client-dev@mozilla.com"],
     "expires_in_version": "never",
     "kind": "count",
     "keyed": true,
     "description": "a testing histogram; not meant to be touched"
   },
-    "TELEMETRY_TEST_KEYED_BOOLEAN": {
+  "TELEMETRY_TEST_KEYED_BOOLEAN": {
     "alert_emails": ["telemetry-client-dev@mozilla.com"],
     "expires_in_version": "never",
     "kind": "boolean",
     "keyed": true,
     "bug_numbers": [1299144],
     "description": "a testing histogram; not meant to be touched"
   },
+  "TELEMETRY_TEST_KEYED_CATEGORICAL": {
+    "alert_emails": ["telemetry-client-dev@mozilla.com"],
+    "expires_in_version": "never",
+    "kind": "categorical",
+    "keyed": true,
+    "labels": [
+      "CommonLabel",
+      "Label2",
+      "Label3"
+    ],
+    "bug_numbers": [1347216],
+    "description": "a testing histogram; not meant to be touched"
+  },
   "TELEMETRY_TEST_RELEASE_OPTOUT": {
     "alert_emails": ["telemetry-client-dev@mozilla.com"],
     "expires_in_version": "never",
     "kind": "flag",
     "releaseChannelCollection": "opt-out",
     "description": "a testing histogram; not meant to be touched"
   },
   "TELEMETRY_TEST_RELEASE_OPTIN": {

--- a/toolkit/components/telemetry/TelemetryHistogram.cpp
+++ b/toolkit/components/telemetry/TelemetryHistogram.cpp
@@ -1709,32 +1709,50 @@ internal_JSKeyedHistogram_Add(JSContext 
     LogToBrowserConsole(nsIScriptError::errorFlag, NS_LITERAL_STRING("Not a string"));
     return true;
   }
 
   const uint32_t type = keyed->GetHistogramType();
 
   // If we don't have an argument for the count histogram, assume an increment of 1.
   // Otherwise, make sure to run some sanity checks on the argument.
-  int32_t value = 1;
+  uint32_t value = 1;
+  mozilla::Telemetry::HistogramID id;
   if ((type != base::CountHistogram::COUNT_HISTOGRAM) || (args.length() == 2)) {
     if (args.length() < 2) {
       LogToBrowserConsole(nsIScriptError::errorFlag,
                           NS_LITERAL_STRING("Expected two arguments for this histogram type"));
       return true;
     }
 
-    if (!(args[1].isNumber() || args[1].isBoolean())) {
-      LogToBrowserConsole(nsIScriptError::errorFlag, NS_LITERAL_STRING("Not a number"));
-      return true;
-    }
+    if (args[1].isString() &&
+        NS_SUCCEEDED(keyed->GetEnumId(id)) &&
+        gHistograms[id].histogramType == nsITelemetry::HISTOGRAM_CATEGORICAL) {
+      // For categorical histograms we allow passing a string argument that specifies the label.
+      nsAutoJSString label;
+      if (!label.init(cx, args[1])) {
+        LogToBrowserConsole(nsIScriptError::errorFlag, NS_LITERAL_STRING("Invalid string parameter"));
+        return true;
+      }
+      nsresult rv = gHistograms[id].label_id(NS_ConvertUTF16toUTF8(label).get(), &value);
+      if (NS_FAILED(rv)) {
+        LogToBrowserConsole(nsIScriptError::errorFlag,
+                            NS_LITERAL_STRING("Unknown label for categorical histogram"));
+        return true;
+      }
+    } else {
+      if (!(args[1].isNumber() || args[1].isBoolean())) {
+        LogToBrowserConsole(nsIScriptError::errorFlag, NS_LITERAL_STRING("Not a number"));
+        return true;
+      }
 
-    if (!JS::ToInt32(cx, args[1], &value)) {
-      LogToBrowserConsole(nsIScriptError::errorFlag, NS_LITERAL_STRING("Failed to convert argument"));
-      return true;
+      if (!JS::ToUint32(cx, args[1], &value)) {
+        LogToBrowserConsole(nsIScriptError::errorFlag, NS_LITERAL_STRING("Failed to convert argument"));
+        return true;
+      }
     }
   }
 
   {
     StaticMutexAutoLock locker(gTelemetryHistogramMutex);
     internal_Accumulate(*keyed, NS_ConvertUTF16toUTF8(key), value);
   }
   return true;

--- a/toolkit/components/telemetry/tests/unit/test_TelemetryHistograms.js
+++ b/toolkit/components/telemetry/tests/unit/test_TelemetryHistograms.js
@@ -587,16 +587,42 @@ add_task(function* test_keyed_count_hist
   let allSnapshots = Telemetry.keyedHistogramSnapshots;
   Assert.deepEqual(allSnapshots[KEYED_ID], testSnapShot);
 
   h.clear();
   Assert.deepEqual(h.keys(), []);
   Assert.deepEqual(h.snapshot(), {});
 });
 
+add_task(function* test_keyed_categorical_histogram() {
+  const KEYED_ID = "TELEMETRY_TEST_KEYED_CATEGORICAL";
+  const KEYS = numberRange(0, 5).map(i => "key" + (i + 1));
+
+  let h = Telemetry.getKeyedHistogramById(KEYED_ID);
+
+  for(let k of KEYS) {
+    // Via label or index.
+    for (let v of ["CommonLabel", "Label2", "Label3", "Label3", 0, 0, 1]) {
+      h.add(k, v);
+    }
+  }
+  // Categorical histograms default to 50 linear buckets.
+  let expectedRanges = [];
+  for (let i = 0; i < 51; ++i) {
+    expectedRanges.push(i);
+  }
+
+  for(let k of KEYS) {
+    let snapshot = h.snapshot(k);
+    Assert.equal(snapshot.sum, 6);
+    Assert.deepEqual(snapshot.ranges, expectedRanges);
+    Assert.deepEqual(snapshot.counts.slice(0, 4), [3, 2, 2, 0]);
+  }
+});
+
 add_task(function* test_keyed_flag_histogram() {
   const KEYED_ID = "TELEMETRY_TEST_KEYED_FLAG";
   let h = Telemetry.getKeyedHistogramById(KEYED_ID);
 
   const KEY = "default";
   h.add(KEY, true);
 
   let testSnapshot = {};