--- a/toolkit/components/telemetry/Telemetry.cpp
+++ b/toolkit/components/telemetry/Telemetry.cpp
@@ -2795,16 +2795,22 @@ Accumulate(const char* name, uint32_t sa
 
 void
 Accumulate(const char *name, const nsCString& key, uint32_t sample)
 {
   TelemetryHistogram::Accumulate(name, key, sample);
 }
 
 void
+AccumulateCategorical(ID id, const nsCString& label)
+{
+  TelemetryHistogram::AccumulateCategorical(id, label);
+}
+
+void
 AccumulateTimeDelta(ID aHistogram, TimeStamp start, TimeStamp end)
 {
   Accumulate(aHistogram,
              static_cast<uint32_t>((end - start).ToMilliseconds()));
 }
 
 void
 ClearHistogram(ID aId)

--- a/toolkit/components/telemetry/Telemetry.h
+++ b/toolkit/components/telemetry/Telemetry.h
@@ -46,66 +46,92 @@ void CreateStatisticsRecorder();
 void DestroyStatisticsRecorder();
 
 /**
  * Initialize the Telemetry service on the main thread at startup.
  */
 void Init();
 
 /**
- * Adds sample to a histogram defined in TelemetryHistograms.h
+ * Adds sample to a histogram defined in TelemetryHistogramEnums.h
  *
  * @param id - histogram id
  * @param sample - value to record.
  */
 void Accumulate(ID id, uint32_t sample);
 
 /**
- * Adds sample to a keyed histogram defined in TelemetryHistograms.h
+ * Adds sample to a keyed histogram defined in TelemetryHistogramEnums.h
  *
  * @param id - keyed histogram id
  * @param key - the string key
  * @param sample - (optional) value to record, defaults to 1.
  */
 void Accumulate(ID id, const nsCString& key, uint32_t sample = 1);
 
 /**
- * Adds a sample to a histogram defined in TelemetryHistograms.h.
+ * Adds a sample to a histogram defined in TelemetryHistogramEnums.h.
  * This function is here to support telemetry measurements from Java,
  * where we have only names and not numeric IDs.  You should almost
  * certainly be using the by-enum-id version instead of this one.
  *
  * @param name - histogram name
  * @param sample - value to record
  */
 void Accumulate(const char* name, uint32_t sample);
 
 /**
- * Adds a sample to a histogram defined in TelemetryHistograms.h.
+ * Adds a sample to a histogram defined in TelemetryHistogramEnums.h.
  * This function is here to support telemetry measurements from Java,
  * where we have only names and not numeric IDs.  You should almost
  * certainly be using the by-enum-id version instead of this one.
  *
  * @param name - histogram name
  * @param key - the string key
  * @param sample - sample - (optional) value to record, defaults to 1.
  */
 void Accumulate(const char *name, const nsCString& key, uint32_t sample = 1);
 
 /**
- * Adds time delta in milliseconds to a histogram defined in TelemetryHistograms.h
+ * Adds sample to a categorical histogram defined in TelemetryHistogramEnums.h
+ * This is the typesafe - and preferred - way to use the categorical histograms
+ * by passing values from the corresponding Telemetry::LABELS_* enum.
+ *
+ * @param enumValue - Label value from one of the Telemetry::LABELS_* enums.
+ */
+template<class E>
+void AccumulateCategorical(E enumValue) {
+  static_assert(IsCategoricalLabelEnum<E>::value,
+                "Only categorical label enum types are supported.");
+  Accumulate(static_cast<ID>(CategoricalLabelId<E>::value),
+             static_cast<uint32_t>(enumValue));
+};
+
+/**
+ * Adds sample to a categorical histogram defined in TelemetryHistogramEnums.h
+ * This string will be matched against the labels defined in Histograms.json.
+ * If the string does not match a label defined for the histogram, nothing will
+ * be recorded.
+ *
+ * @param id - The histogram id.
+ * @param label - A string label value that is defined in Histograms.json for this histogram.
+ */
+void AccumulateCategorical(ID id, const nsCString& label);
+
+/**
+ * Adds time delta in milliseconds to a histogram defined in TelemetryHistogramEnums.h
  *
  * @param id - histogram id
  * @param start - start time
  * @param end - end time
  */
 void AccumulateTimeDelta(ID id, TimeStamp start, TimeStamp end = TimeStamp::Now());
 
 /**
- * This clears the data for a histogram in TelemetryHistograms.h.
+ * This clears the data for a histogram in TelemetryHistogramEnums.h.
  *
  * @param id - histogram id
  */
 void ClearHistogram(ID id);
 
 /**
  * Enable/disable recording for this histogram at runtime.
  * Recording is enabled by default, unless listed at kRecordingInitiallyDisabledIDs[].

--- a/toolkit/components/telemetry/TelemetryHistogram.cpp
+++ b/toolkit/components/telemetry/TelemetryHistogram.cpp
@@ -592,16 +592,33 @@ internal_HistogramAdd(Histogram& histogr
       return NS_OK;
     }
     dataset = gHistograms[id].dataset;
   }
 
   return internal_HistogramAdd(histogram, value, dataset);
 }
 
+nsresult
+internal_HistogramAddCategorical(mozilla::Telemetry::ID id, const nsCString& label)
+{
+  uint32_t labelId = 0;
+  if (NS_FAILED(gHistograms[id].label_id(label.get(), &labelId))) {
+    return NS_ERROR_ILLEGAL_VALUE;
+  }
+
+  Histogram* h = nullptr;
+  nsresult rv = internal_GetHistogramByEnumId(id, &h);
+  if (NS_FAILED(rv)) {
+    return rv;
+  }
+
+  return internal_HistogramAdd(*h, labelId);
+}
+
 void
 internal_HistogramClear(Histogram& aHistogram, bool onlySubsession)
 {
   if (!onlySubsession) {
     aHistogram.Clear();
   }
 
 #if !defined(MOZ_WIDGET_GONK) && !defined(MOZ_WIDGET_ANDROID)
@@ -1105,23 +1122,22 @@ internal_JSHistogram_Add(JSContext *cx, 
       NS_SUCCEEDED(internal_GetHistogramEnumId(h->histogram_name().c_str(), &id)) &&
       gHistograms[id].histogramType == nsITelemetry::HISTOGRAM_CATEGORICAL) {
     nsAutoJSString label;
     if (!label.init(cx, args[0])) {
       JS_ReportError(cx, "Invalid string parameter");
       return false;
     }
 
-    uint32_t labelId = 0;
-    if (NS_FAILED(gHistograms[id].label_id(NS_ConvertUTF16toUTF8(label).get(), &labelId))) {
+    nsresult rv = internal_HistogramAddCategorical(id, NS_ConvertUTF16toUTF8(label));
+    if (NS_FAILED(rv)) {
       JS_ReportError(cx, "Unknown label for categorical histogram");
       return false;
     }
 
-    internal_HistogramAdd(*h, labelId);
     return true;
   }
 
   // All other accumulations expect one numerical argument.
   int32_t value = 0;
   if (!args.length()) {
     JS_ReportError(cx, "Expected one argument");
     return false;
@@ -1930,16 +1946,24 @@ TelemetryHistogram::Accumulate(const cha
   mozilla::Telemetry::ID id;
   nsresult rv = internal_GetHistogramEnumId(name, &id);
   if (NS_SUCCEEDED(rv)) {
     internal_Accumulate(id, key, sample);
   }
 }
 
 void
+TelemetryHistogram::AccumulateCategorical(mozilla::Telemetry::ID aId,
+                                          const nsCString& label)
+{
+  StaticMutexAutoLock locker(gTelemetryHistogramMutex);
+  internal_HistogramAddCategorical(aId, label);
+}
+
+void
 TelemetryHistogram::ClearHistogram(mozilla::Telemetry::ID aId)
 {
   StaticMutexAutoLock locker(gTelemetryHistogramMutex);
   if (!internal_CanRecordBase()) {
     return;
   }
 
   Histogram *h;

--- a/toolkit/components/telemetry/TelemetryHistogram.h
+++ b/toolkit/components/telemetry/TelemetryHistogram.h
@@ -35,16 +35,18 @@ void SetHistogramRecordingEnabled(mozill
 nsresult SetHistogramRecordingEnabled(const nsACString &id, bool aEnabled);
 
 void Accumulate(mozilla::Telemetry::ID aHistogram, uint32_t aSample);
 void Accumulate(mozilla::Telemetry::ID aID, const nsCString& aKey,
                                             uint32_t aSample);
 void Accumulate(const char* name, uint32_t sample);
 void Accumulate(const char* name, const nsCString& key, uint32_t sample);
 
+void AccumulateCategorical(mozilla::Telemetry::ID aId, const nsCString& aLabel);
+
 void
 ClearHistogram(mozilla::Telemetry::ID aId);
 
 nsresult
 GetHistogramById(const nsACString &name, JSContext *cx,
                  JS::MutableHandle<JS::Value> ret);
 
 nsresult

--- a/toolkit/components/telemetry/gen-histogram-enum.py
+++ b/toolkit/components/telemetry/gen-histogram-enum.py
@@ -16,31 +16,47 @@ from __future__ import print_function
 
 import histogram_tools
 import itertools
 import sys
 
 banner = """/* This file is auto-generated, see gen-histogram-enum.py.  */
 """
 
+header = """
+#ifndef mozilla_TelemetryHistogramEnums_h
+#define mozilla_TelemetryHistogramEnums_h
+
+#include "mozilla/TemplateLib.h"
+
+namespace mozilla {
+namespace Telemetry {
+"""
+
+footer = """
+} // namespace mozilla
+} // namespace Telemetry
+#endif // mozilla_TelemetryHistogramEnums_h"""
+
 def main(output, *filenames):
+    # Print header.
     print(banner, file=output)
-    print("#ifndef mozilla_TelemetryHistogramEnums_h", file=output);
-    print("#define mozilla_TelemetryHistogramEnums_h", file=output);
-    print("namespace mozilla {", file=output)
-    print("namespace Telemetry {", file=output)
-    print("enum ID : uint32_t {", file=output)
+    print(header, file=output)
 
-    groups = itertools.groupby(histogram_tools.from_files(filenames),
+    # Load the histograms.
+    all_histograms = list(histogram_tools.from_files(filenames))
+    groups = itertools.groupby(all_histograms,
                                lambda h: h.name().startswith("USE_COUNTER2_"))
-    seen_use_counters = False
 
+    # Print the histogram enums.
     # Note that histogram_tools.py guarantees that all of the USE_COUNTER2_*
     # histograms are defined in a contiguous block.  We therefore assume
     # that there's at most one group for which use_counter_group is true.
+    print("enum ID : uint32_t {", file=output)
+    seen_use_counters = False
     for (use_counter_group, histograms) in groups:
         if use_counter_group:
             seen_use_counters = True
 
         # The HistogramDUMMY* enum variables are used to make the computation
         # of Histogram{First,Last}UseCounter easier.  Otherwise, we'd have to
         # special case the first and last histogram in the group.
         if use_counter_group:
@@ -62,14 +78,30 @@ def main(output, *filenames):
     print("  HistogramCount,", file=output)
     if seen_use_counters:
         print("  HistogramUseCounterCount = HistogramLastUseCounter - HistogramFirstUseCounter + 1", file=output)
     else:
         print("  HistogramFirstUseCounter = 0,", file=output)
         print("  HistogramLastUseCounter = 0,", file=output)
         print("  HistogramUseCounterCount = 0", file=output)
     print("};", file=output)
-    print("} // namespace mozilla", file=output)
-    print("} // namespace Telemetry", file=output)
-    print("#endif // mozilla_TelemetryHistogramEnums_h", file=output);
+
+    # Write categorical label enums.
+    categorical = filter(lambda h: h.kind() == "categorical", all_histograms)
+    enums = [("LABELS_" + h.name(), h.labels(), h.name()) for h in categorical]
+    for name,labels,_ in enums:
+        print("\nenum class %s : uint32_t {" % name, file=output)
+        print("  %s" % ",\n  ".join(labels), file=output)
+        print("};", file=output)
+
+    print("\ntemplate<class T> struct IsCategoricalLabelEnum : FalseType {};", file=output)
+    for name,_,_ in enums:
+        print("template<> struct IsCategoricalLabelEnum<%s> : TrueType {};" % name, file=output)
+
+    print("\ntemplate<class T> struct CategoricalLabelId {};", file=output)
+    for name,_,id in enums:
+        print("template<> struct CategoricalLabelId<%s> : IntegralConstant<uint32_t, %s> {};" % (name, id), file=output)
+
+    # Footer.
+    print(footer, file=output)
 
 if __name__ == '__main__':
     main(sys.stdout, *sys.argv[1:])

--- a/toolkit/components/telemetry/histogram_tools.py
+++ b/toolkit/components/telemetry/histogram_tools.py
@@ -239,16 +239,20 @@ associated with the histogram.  Returns 
         self.check_whitelistable_fields(name, definition)
         self.check_expiration(name, definition)
         self.check_label_values(name, definition)
 
     def check_name(self, name):
         if '#' in name:
             raise ValueError, '"#" not permitted for %s' % (name)
 
+        # Avoid C++ identifier conflicts between histogram enums and label enum names.
+        if name.startswith("LABELS_"):
+            raise ValueError, "Histogram name '%s' can not start with LABELS_" % (name)
+
     def check_expiration(self, name, definition):
         expiration = definition.get('expires_in_version')
 
         if not expiration:
             return
 
         if re.match(r'^[1-9][0-9]*$', expiration):
             expiration = expiration + ".0a1"