--- a/toolkit/components/places/Helpers.cpp
+++ b/toolkit/components/places/Helpers.cpp
@@ -204,43 +204,28 @@ void
 ReverseString(const nsString& aInput, nsString& aReversed)
 {
   aReversed.Truncate(0);
   for (int32_t i = aInput.Length() - 1; i >= 0; i--) {
     aReversed.Append(aInput[i]);
   }
 }
 
-#ifdef XP_WIN
-} // namespace places
-} // namespace mozilla
-
-// Included here because windows.h conflicts with the use of mozIStorageError
-// above, but make sure that these are not included inside mozilla::places.
-#include <windows.h>
-#include <wincrypt.h>
-
-namespace mozilla {
-namespace places {
-#endif
-
 static
 nsresult
 GenerateRandomBytes(uint32_t aSize,
                     uint8_t* _buffer)
 {
   // On Windows, we'll use its built-in cryptographic API.
 #if defined(XP_WIN)
+  const nsNavHistory* history = nsNavHistory::GetConstHistoryService();
   HCRYPTPROV cryptoProvider;
-  BOOL rc = CryptAcquireContext(&cryptoProvider, 0, 0, PROV_RSA_FULL,
-                                CRYPT_VERIFYCONTEXT | CRYPT_SILENT);
-  if (rc) {
-    rc = CryptGenRandom(cryptoProvider, aSize, _buffer);
-    (void)CryptReleaseContext(cryptoProvider, 0);
-  }
+  nsresult rv = history->GetCryptoProvider(cryptoProvider);
+  NS_ENSURE_SUCCESS(rv, rv);
+  BOOL rc = CryptGenRandom(cryptoProvider, aSize, _buffer);
   return rc ? NS_OK : NS_ERROR_FAILURE;
 
   // On Unix, we'll just read in from /dev/urandom.
 #elif defined(XP_UNIX)
   NS_ENSURE_ARG_MAX(aSize, INT32_MAX);
   PRFileDesc* urandom = PR_Open("/dev/urandom", PR_RDONLY, 0);
   nsresult rv = NS_ERROR_FAILURE;
   if (urandom) {

--- a/toolkit/components/places/nsNavHistory.cpp
+++ b/toolkit/components/places/nsNavHistory.cpp
@@ -282,31 +282,48 @@ nsNavHistory::nsNavHistory()
   , mHistoryEnabled(true)
   , mNumVisitsForFrecency(10)
   , mTagsFolder(-1)
   , mDaysOfHistory(-1)
   , mLastCachedStartOfDay(INT64_MAX)
   , mLastCachedEndOfDay(0)
   , mCanNotify(true)
   , mCacheObservers("history-observers")
+#ifdef XP_WIN
+  , mCryptoProviderInitialized(false)
+#endif
 {
   NS_ASSERTION(!gHistoryService,
                "Attempting to create two instances of the service!");
+#ifdef XP_WIN
+  BOOL cryptoAcquired = CryptAcquireContext(&mCryptoProvider, 0, 0, PROV_RSA_FULL,
+                                            CRYPT_VERIFYCONTEXT | CRYPT_SILENT);
+  if (cryptoAcquired) {
+    mCryptoProviderInitialized = true;
+  }
+#endif
   gHistoryService = this;
 }
 
 
 nsNavHistory::~nsNavHistory()
 {
   // remove the static reference to the service. Check to make sure its us
   // in case somebody creates an extra instance of the service.
   NS_ASSERTION(gHistoryService == this,
                "Deleting a non-singleton instance of the service");
+
   if (gHistoryService == this)
     gHistoryService = nullptr;
+
+#ifdef XP_WIN
+  if (mCryptoProviderInitialized) {
+    Unused << CryptReleaseContext(mCryptoProvider, 0);
+  }
+#endif
 }
 
 
 nsresult
 nsNavHistory::Init()
 {
   LoadPrefs();
 

--- a/toolkit/components/places/nsNavHistory.h
+++ b/toolkit/components/places/nsNavHistory.h
@@ -24,16 +24,21 @@
 #include "nsTHashtable.h"
 
 #include "nsNavHistoryResult.h"
 #include "nsNavHistoryQuery.h"
 #include "Database.h"
 #include "mozilla/Attributes.h"
 #include "mozilla/Atomics.h"
 
+#ifdef XP_WIN
+#include "WinUtils.h"
+#include <wincrypt.h>
+#endif
+
 #define QUERYUPDATE_TIME 0
 #define QUERYUPDATE_SIMPLE 1
 #define QUERYUPDATE_COMPLEX 2
 #define QUERYUPDATE_COMPLEX_WITH_BOOKMARKS 3
 #define QUERYUPDATE_HOST 4
 
 // Clamp title and URL to generously large, but not too large, length.
 // See bug 319004 for details.
@@ -483,16 +488,27 @@ public:
 
   static void StoreLastInsertedId(const nsACString& aTable,
                                   const int64_t aLastInsertedId);
 
   bool isBatching() {
     return mBatchLevel > 0;
   }
 
+#ifdef XP_WIN
+  /**
+   * Get the cached HCRYPTPROV initialized in the nsNavHistory constructor.
+   */
+  nsresult GetCryptoProvider(HCRYPTPROV& aCryptoProvider) const {
+    NS_ENSURE_STATE(mCryptoProviderInitialized);
+    aCryptoProvider = mCryptoProvider;
+    return NS_OK;
+  }
+#endif
+
 private:
   ~nsNavHistory();
 
   // used by GetHistoryService
   static nsNavHistory *gHistoryService;
 
 protected:
 
@@ -637,16 +653,23 @@ protected:
 
   int32_t mDaysOfHistory;
   int64_t mLastCachedStartOfDay;
   int64_t mLastCachedEndOfDay;
 
   // Used to enable and disable the observer notifications
   bool mCanNotify;
   nsCategoryCache<nsINavHistoryObserver> mCacheObservers;
+
+  // Used to cache the call to CryptAcquireContext, which is expensive
+  // when called thousands of times
+#ifdef XP_WIN
+  HCRYPTPROV mCryptoProvider;
+  bool mCryptoProviderInitialized;
+#endif
 };
 
 
 #define PLACES_URI_PREFIX "place:"
 
 /* Returns true if the given URI represents a history query. */
 inline bool IsQueryURI(const nsCString &uri)
 {