--- a/toolkit/components/telemetry/TelemetryHistogram.cpp
+++ b/toolkit/components/telemetry/TelemetryHistogram.cpp
@@ -1311,16 +1311,19 @@ internal_RemoteAccumulate(mozilla::Telem
 {
   if (XRE_IsParentProcess()) {
     return false;
   }
   const HistogramInfo& th = gHistograms[aId];
   KeyedHistogram* keyed
      = internal_GetKeyedHistogramById(nsDependentCString(th.id()));
   MOZ_ASSERT(keyed);
+  // Assert on empty keys as well, we should be filtering them out in
+  // the outer API.
+  MOZ_ASSERT(!aKey.IsEmpty());
   if (!keyed->IsRecordingEnabled()) {
     return false;
   }
   TelemetryIPCAccumulator::AccumulateChildKeyedHistogram(aId, aKey, aSample);
   return true;
 }
 
 void internal_Accumulate(mozilla::Telemetry::HistogramID aHistogram, uint32_t aSample)
@@ -1738,16 +1741,22 @@ internal_JSKeyedHistogram_Add(JSContext 
   }
 
   nsAutoJSString key;
   if (!args[0].isString() || !key.init(cx, args[0])) {
     LogToBrowserConsole(nsIScriptError::errorFlag, NS_LITERAL_STRING("Not a string"));
     return true;
   }
 
+  if (key.IsEmpty()) {
+    LogToBrowserConsole(nsIScriptError::errorFlag,
+      NS_LITERAL_STRING("Empty histogram keys are not allowed."));
+    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;
   if ((type != base::CountHistogram::COUNT_HISTOGRAM) || (args.length() == 2)) {
     if (args.length() < 2) {
       LogToBrowserConsole(nsIScriptError::errorFlag,
@@ -2131,16 +2140,22 @@ void
 TelemetryHistogram::Accumulate(mozilla::Telemetry::HistogramID aID,
                                const nsCString& aKey, uint32_t aSample)
 {
   if (NS_WARN_IF(!internal_IsHistogramEnumId(aID))) {
     MOZ_ASSERT_UNREACHABLE("Histogram usage requires valid ids.");
     return;
   }
 
+  if (aKey.IsEmpty()) {
+    LogToBrowserConsole(nsIScriptError::errorFlag,
+      NS_LITERAL_STRING("Empty histogram keys are not allowed."));
+    return;
+  }
+
   StaticMutexAutoLock locker(gTelemetryHistogramMutex);
   internal_Accumulate(aID, aKey, aSample);
 }
 
 void
 TelemetryHistogram::Accumulate(const char* name, uint32_t sample)
 {
   StaticMutexAutoLock locker(gTelemetryHistogramMutex);
@@ -2154,16 +2169,22 @@ TelemetryHistogram::Accumulate(const cha
   }
   internal_Accumulate(id, sample);
 }
 
 void
 TelemetryHistogram::Accumulate(const char* name,
                                const nsCString& key, uint32_t sample)
 {
+  if (key.IsEmpty()) {
+    LogToBrowserConsole(nsIScriptError::errorFlag,
+      NS_LITERAL_STRING("Empty histogram keys are not allowed."));
+    return;
+  }
+
   StaticMutexAutoLock locker(gTelemetryHistogramMutex);
   if (!internal_CanRecordBase()) {
     return;
   }
   mozilla::Telemetry::HistogramID id;
   nsresult rv = internal_GetHistogramEnumId(name, &id);
   if (NS_SUCCEEDED(rv)) {
     internal_Accumulate(id, key, sample);

--- a/toolkit/components/telemetry/docs/collection/histograms.rst
+++ b/toolkit/components/telemetry/docs/collection/histograms.rst
@@ -84,17 +84,21 @@ Flag histograms will ignore any changes 
 *Deprecated* (please use uint :doc:`scalars`).
 
 This histogram type is used when you want to record a count of something. It only stores a single value and defaults to `0`.
 
 Keyed Histograms
 ----------------
 
 Keyed histograms are collections of one of the histogram types above, indexed by a string key. This is for example useful when you want to break down certain counts by a name, like how often searches happen with which search engine.
-Note that when you need to record for a small set of known keys, using separate plain histograms is more efficient.
+
+Note that:
+
+- keys can't be empty strings;
+- when you need to record for a small set of known keys, using separate plain histograms is more efficient.
 
 .. warning::
 
     Keyed histograms are currently not supported in the `histogram change detector <https://alerts.telemetry.mozilla.org/index.html>`_.
 
 Declaring a Histogram
 =====================
 
@@ -198,17 +202,21 @@ A Telemetry probe is the code that measu
 .. code-block:: js
 
   let histogram = Services.telemetry.getHistogramById("PLACES_AUTOCOMPLETE_1ST_RESULT_TIME_MS");
   histogram.add(measuredDuration);
 
   let keyed = Services.telemetry.getKeyedHistogramById("TAG_SEEN_COUNTS");
   keyed.add("blink");
 
-Note that ``nsITelemetry.getHistogramById()`` will throw an ``NS_ERROR_ILLEGAL_VALUE`` JavaScript exception if it is called with an invalid histogram ID. The ``add()`` function will not throw if it fails, instead it prints an error in the browser console.
+Note that:
+
+- ``nsITelemetry.getHistogramById()`` will throw an ``NS_ERROR_ILLEGAL_VALUE`` JavaScript exception if it is called with an invalid histogram ID;
+- the ``add()`` function will not throw on failure, but log an error to the browser console;
+- for keyed histograms, calling ``add()`` with an empty key will be ignored and log an error.
 
 For histograms measuring time, `TelemetryStopwatch <https://mxr.mozilla.org/mozilla-central/source/toolkit/components/telemetry/TelemetryStopwatch.jsm>`_ can be used to avoid working with Dates manually:
 
 .. code-block:: js
 
   TelemetryStopwatch.start("SEARCH_SERVICE_INIT_MS");
   TelemetryStopwatch.finish("SEARCH_SERVICE_INIT_MS");
 

--- a/toolkit/components/telemetry/tests/unit/test_TelemetryHistograms.js
+++ b/toolkit/components/telemetry/tests/unit/test_TelemetryHistograms.js
@@ -482,16 +482,25 @@ add_task(function* test_keyed_histogram(
   let threw = false;
   try {
     Telemetry.getKeyedHistogramById("test::unknown histogram", "never", Telemetry.HISTOGRAM_BOOLEAN);
   } catch (e) {
     // This should throw as it is an unknown ID
     threw = true;
   }
   Assert.ok(threw, "getKeyedHistogramById should have thrown");
+
+  // Check that empty keys are not allowed.
+  const KEYED_ID = "TELEMETRY_TEST_KEYED_COUNT";
+  let h = Telemetry.getKeyedHistogramById(KEYED_ID);
+
+  // Try to add to an empty key and make sure nothing happens.
+  h.add("");
+  Assert.ok(!("" in h.snapshot()),
+            "Keyed histogram should not allow empty keys.");
 });
 
 add_task(function* test_keyed_boolean_histogram() {
   const KEYED_ID = "TELEMETRY_TEST_KEYED_BOOLEAN";
   let KEYS = numberRange(0, 2).map(i => "key" + (i + 1));
   KEYS.push("漢語");
   let histogramBase = {
     "min": 1,