diff --git a/src/applications/diffusion/query/blame/DiffusionBlameQuery.php b/src/applications/diffusion/query/blame/DiffusionBlameQuery.php
--- a/src/applications/diffusion/query/blame/DiffusionBlameQuery.php
+++ b/src/applications/diffusion/query/blame/DiffusionBlameQuery.php
@@ -34,9 +34,35 @@
 
   final protected function executeQuery() {
     $paths = $this->getPaths();
+
+    $blame = array();
+
+    // Load cache keys: these are the commits at which each path was last
+    // touched.
+    $keys = $this->loadCacheKeys($paths);
+
+    // Try to read blame data from cache.
+    $cache = $this->readCacheData($keys);
+    foreach ($paths as $key => $path) {
+      if (!isset($cache[$path])) {
+        continue;
+      }
+
+      $blame[$path] = $cache[$path];
+      unset($paths[$key]);
+    }
+
+    // If we have no paths left, we filled everything from cache and can
+    // bail out early.
+    if (!$paths) {
+      return $blame;
+    }
+
     $request = $this->getRequest();
     $timeout = $this->getTimeout();
 
+    // We're still missing at least some data, so we need to run VCS commands
+    // to pull it.
     $futures = array();
     foreach ($paths as $path) {
       $future = $this->newBlameFuture($request, $path);
@@ -48,22 +74,107 @@
       $futures[$path] = $future;
     }
 
+    $futures = id(new FutureIterator($futures))
+      ->limit(4);
 
-    $blame = array();
+    foreach ($futures as $path => $future) {
+      $path_blame = $this->resolveBlameFuture($future);
+      if ($path_blame !== null) {
+        $blame[$path] = $path_blame;
+      }
+    }
+
+    // Fill the cache with anything we generated.
+    $this->writeCacheData(
+      array_select_keys($keys, $paths),
+      $blame);
 
-    if ($futures) {
-      $futures = id(new FutureIterator($futures))
-        ->limit(4);
+    return $blame;
+  }
 
-      foreach ($futures as $path => $future) {
-        $path_blame = $this->resolveBlameFuture($future);
-        if ($path_blame !== null) {
-          $blame[$path] = $path_blame;
-        }
+  private function loadCacheKeys(array $paths) {
+    $request = $this->getRequest();
+    $viewer = $request->getUser();
+
+    $repository = $request->getRepository();
+    $repository_id = $repository->getID();
+
+    $last_modified = parent::callConduitWithDiffusionRequest(
+      $viewer,
+      $request,
+      'diffusion.lastmodifiedquery',
+      array(
+        'paths' => array_fill_keys($paths, $request->getCommit()),
+      ));
+
+    $map = array();
+    foreach ($paths as $path) {
+      $identifier = idx($last_modified, $path);
+      if ($identifier === null) {
+        continue;
       }
+
+      $map[$path] = "blame({$repository_id}, {$identifier}, {$path}, raw)";
     }
 
-    return $blame;
+    return $map;
+  }
+
+  private function readCacheData(array $keys) {
+    $cache = PhabricatorCaches::getImmutableCache();
+    $data = $cache->getKeys($keys);
+
+    $results = array();
+    foreach ($keys as $path => $key) {
+      if (!isset($data[$key])) {
+        continue;
+      }
+      $results[$path] = $data[$key];
+    }
+
+    // Decode the cache storage format.
+    foreach ($results as $path => $cache) {
+      list($head, $body) = explode("\n", $cache, 2);
+      switch ($head) {
+        case 'raw':
+          $body = explode("\n", $body);
+          break;
+        default:
+          $body = null;
+          break;
+      }
+
+      if ($body === null) {
+        unset($results[$path]);
+      } else {
+        $results[$path] = $body;
+      }
+    }
+
+    return $results;
+  }
+
+  private function writeCacheData(array $keys, array $blame) {
+    $writes = array();
+    foreach ($keys as $path => $key) {
+      $value = idx($blame, $path);
+      if ($value === null) {
+        continue;
+      }
+
+      // For now, just store the entire value with a "raw" header. In the
+      // future, we could compress this or use IDs instead.
+      $value = "raw\n".implode("\n", $value);
+
+      $writes[$key] = $value;
+    }
+
+    if (!$writes) {
+      return;
+    }
+
+    $cache = PhabricatorCaches::getImmutableCache();
+    $data = $cache->setKeys($writes, phutil_units('14 days in seconds'));
   }
 
 }
diff --git a/src/applications/repository/query/PhabricatorRepositoryQuery.php b/src/applications/repository/query/PhabricatorRepositoryQuery.php
--- a/src/applications/repository/query/PhabricatorRepositoryQuery.php
+++ b/src/applications/repository/query/PhabricatorRepositoryQuery.php
@@ -49,6 +49,8 @@
   }
 
   public function withIdentifiers(array $identifiers) {
+    $identifiers = array_fuse($identifiers);
+
     $ids = array();
     $callsigns = array();
     $phids = array();