--- a/security/manager/ssl/public/nsICertOverrideService.idl
+++ b/security/manager/ssl/public/nsICertOverrideService.idl
@@ -13,17 +13,17 @@ interface nsIX509Cert;
 #define NS_CERTOVERRIDE_CONTRACTID "@mozilla.org/security/certoverride;1"
 %}
 
 /**
  * This represents the global list of triples
  *   {host:port, cert-fingerprint, allowed-overrides} 
  * that the user wants to accept without further warnings. 
  */
-[scriptable, uuid(31738d2a-77d3-4359-84c9-4be2f38fb8c5)]
+[scriptable, uuid(be019e47-22fc-4355-9f16-9ab047d6742d)]
 interface nsICertOverrideService : nsISupports {
 
   /**
    *  Override Untrusted
    */
   const short ERROR_UNTRUSTED = 1;
 
   /**
@@ -104,23 +104,21 @@ interface nsICertOverrideService : nsISu
    *               If it is -1, then it is internaly treated as 443.
    *               If it is 0 and aHostName is "all:temporary-certificates",
    *               then all temporary certificates should be cleared.
    */
   void clearValidityOverride(in ACString aHostName,
                              in int32_t aPort);
 
   /**
-   *  Obtain the full list of hostname:port for which overrides are known.
+   *  Count and return the number of permanent overrides.
    *
-   *  @param aCount The number of host:port entries returned
-   *  @param aHostsWithPortsArray The array of host:port entries returned
+   *  @param aCount The number of permanent overrides
    */
-  void getAllOverrideHostsWithPorts(out uint32_t aCount, 
-                                    [array, size_is(aCount)] out wstring aHostsWithPortsArray);
+  void getPermanentOverrideCount(out uint32_t aCount);
 
   /**
    *  Is the given cert used in rules?
    *
    *  @param aCert The cert we're looking for
    *  @return how many override entries are currently on file
    *          for the given certificate
    */

--- a/security/manager/ssl/src/nsCertOverrideService.cpp
+++ b/security/manager/ssl/src/nsCertOverrideService.cpp
@@ -608,21 +608,38 @@ nsCertOverrideService::ClearValidityOver
     SSL_ClearSessionCache();
   } else {
     return NS_ERROR_NOT_AVAILABLE;
   }
 
   return NS_OK;
 }
 
+static PLDHashOperator
+CountPermanentEntriesCallback(nsCertOverrideEntry* aEntry, void* aArg)
+{
+  uint32_t* overrideCount = reinterpret_cast<uint32_t*>(aArg);
+  if (aEntry && !aEntry->mSettings.mIsTemporary) {
+    *overrideCount = *overrideCount + 1;
+    return PL_DHASH_NEXT;
+  }
+
+  return PL_DHASH_NEXT;
+}
+
 NS_IMETHODIMP
-nsCertOverrideService::GetAllOverrideHostsWithPorts(uint32_t *aCount, 
-                                                        char16_t ***aHostsWithPortsArray)
+nsCertOverrideService::GetPermanentOverrideCount(uint32_t* aOverrideCount)
 {
-  return NS_ERROR_NOT_IMPLEMENTED;
+  NS_ENSURE_ARG(aOverrideCount);
+  *aOverrideCount = 0;
+
+  ReentrantMonitorAutoEnter lock(monitor);
+  mSettingsTable.EnumerateEntries(CountPermanentEntriesCallback, aOverrideCount);
+
+  return NS_OK;
 }
 
 static bool
 matchesDBKey(nsIX509Cert *cert, const char *match_dbkey)
 {
   char *dbkey = nullptr;
   nsresult rv = cert->GetDbKey(&dbkey);
   if (NS_FAILED(rv) || !dbkey)

--- a/security/manager/ssl/src/nsNSSComponent.cpp
+++ b/security/manager/ssl/src/nsNSSComponent.cpp
@@ -1044,16 +1044,33 @@ nsNSSComponent::InitializeNSS()
   // Initialize the site security service
   nsCOMPtr<nsISiteSecurityService> sssService =
     do_GetService(NS_SSSERVICE_CONTRACTID);
   if (!sssService) {
     PR_LOG(gPIPNSSLog, PR_LOG_DEBUG, ("Cannot initialize site security service\n"));
     return NS_ERROR_FAILURE;
   }
 
+  // This can happen during startup and is a bit expensive, so only instantiate
+  // the certificate override service if telemetry is actually enabled.
+  if (Telemetry::CanRecord()) {
+    nsCOMPtr<nsICertOverrideService> overrideService(
+      do_GetService(NS_CERTOVERRIDE_CONTRACTID));
+    if (!overrideService) {
+      PR_LOG(gPIPNSSLog, PR_LOG_DEBUG, ("Failed to initialize cert override service\n"));
+      return NS_ERROR_FAILURE;
+    }
+    uint32_t overrideCount = 0;
+    rv = overrideService->GetPermanentOverrideCount(&overrideCount);
+    if (NS_FAILED(rv)) {
+      return rv;
+    }
+    Telemetry::Accumulate(Telemetry::SSL_PERMANENT_CERT_ERROR_OVERRIDES,
+                          overrideCount);
+  }
 
   PR_LOG(gPIPNSSLog, PR_LOG_DEBUG, ("NSS Initialization done\n"));
   return NS_OK;
 }
 
 void
 nsNSSComponent::ShutdownNSS()
 {

--- a/toolkit/components/telemetry/Histograms.json
+++ b/toolkit/components/telemetry/Histograms.json
@@ -6473,16 +6473,23 @@
     "description": "For non-stapling cases, is OCSP fetching a possibility? (0=yes, 1=no because missing/invalid OCSP URI, 2=no because fetching disabled, 3=no because both)"
   },
   "SSL_CERT_ERROR_OVERRIDES": {
     "expires_in_version": "never",
     "kind": "enumerated",
     "n_values": 24,
     "description": "Was a certificate error overridden on this handshake? What was it? (0=unknown error (indicating bug), 1=no, >1=a specific error)"
   },
+  "SSL_PERMANENT_CERT_ERROR_OVERRIDES": {
+    "expires_in_version": "never",
+    "kind": "exponential",
+    "high": 1024,
+    "n_buckets": 10,
+    "description": "How many permanent certificate overrides a user has stored."
+  },
   "TELEMETRY_TEST_EXPIRED": {
     "expires_in_version": "4.0a1",
     "kind": "flag",
     "description": "a testing histogram; not meant to be touched"
   },
   "CERT_OCSP_ENABLED": {
     "expires_in_version": "never",
     "kind": "boolean",