diff --git a/polygerrit-ui/app/elements/core/gr-router/gr-router.html b/polygerrit-ui/app/elements/core/gr-router/gr-router.html
index f07daa5..2ef65f4 100644
--- a/polygerrit-ui/app/elements/core/gr-router/gr-router.html
+++ b/polygerrit-ui/app/elements/core/gr-router/gr-router.html
@@ -23,6 +23,9 @@
 <link rel="import" href="../gr-reporting/gr-reporting.html">
 
 <dom-module id="gr-router">
+  <template>
+    <gr-rest-api-interface id="restAPI"></gr-rest-api-interface>
+  </template>
   <script src="../../../bower_components/page/page.js"></script>
   <script src="gr-router.js"></script>
 </dom-module>
diff --git a/polygerrit-ui/app/elements/core/gr-router/gr-router.js b/polygerrit-ui/app/elements/core/gr-router/gr-router.js
index acc9d4f..93bddcb 100644
--- a/polygerrit-ui/app/elements/core/gr-router/gr-router.js
+++ b/polygerrit-ui/app/elements/core/gr-router/gr-router.js
@@ -154,10 +154,6 @@
     is: 'gr-router',
 
     properties: {
-      _restAPI: {
-        type: Object,
-        value: () => document.createElement('gr-rest-api-interface'),
-      },
       _app: {
         type: Object,
         value: app,
@@ -277,8 +273,12 @@
     _normalizeLegacyRouteParams(params) {
       if (!params.changeNum) { return Promise.resolve(); }
 
-      return this._restAPI.getFromProjectLookup(params.changeNum)
+      return this.$.restAPI.getFromProjectLookup(params.changeNum)
           .then(project => {
+            // Do nothing if the lookup request failed. This avoids an infinite
+            // loop of project lookups.
+            if (!project) { return; }
+
             params.project = project;
             this._normalizePatchRangeParams(params);
             this._redirect(this._generateUrl(params));
@@ -370,7 +370,7 @@
      *     (if it resolves).
      */
     _redirectIfNotLoggedIn(data) {
-      return this._restAPI.getLoggedIn().then(loggedIn => {
+      return this.$.restAPI.getLoggedIn().then(loggedIn => {
         if (loggedIn) {
           return Promise.resolve();
         } else {
@@ -382,7 +382,7 @@
 
     /**  Page.js middleware that warms the REST API's logged-in cache line. */
     _loadUserMiddleware(ctx, next) {
-      this._restAPI.getLoggedIn().then(() => { next(); });
+      this.$.restAPI.getLoggedIn().then(() => { next(); });
     },
 
     /**
@@ -584,7 +584,7 @@
         this._redirect(newUrl);
         return null;
       }
-      return this._restAPI.getLoggedIn().then(loggedIn => {
+      return this.$.restAPI.getLoggedIn().then(loggedIn => {
         if (loggedIn) {
           this._redirect('/dashboard/self');
         } else {
@@ -599,7 +599,7 @@
         return;
       }
 
-      return this._restAPI.getLoggedIn().then(loggedIn => {
+      return this.$.restAPI.getLoggedIn().then(loggedIn => {
         if (!loggedIn) {
           if (data.params[0].toLowerCase() === 'self') {
             this._redirectToLogin(data.canonicalPath);
@@ -937,7 +937,7 @@
         this._redirect(this._generateUrl(params));
       } else {
         this._setParams(params);
-        this._restAPI.setInProjectLookup(params.changeNum,
+        this.$.restAPI.setInProjectLookup(params.changeNum,
             params.project);
       }
     },
diff --git a/polygerrit-ui/app/elements/core/gr-router/gr-router_test.html b/polygerrit-ui/app/elements/core/gr-router/gr-router_test.html
index a9231b6..cb659f8 100644
--- a/polygerrit-ui/app/elements/core/gr-router/gr-router_test.html
+++ b/polygerrit-ui/app/elements/core/gr-router/gr-router_test.html
@@ -183,7 +183,7 @@
     });
 
     test('_redirectIfNotLoggedIn while logged in', () => {
-      sandbox.stub(element._restAPI, 'getLoggedIn')
+      sandbox.stub(element.$.restAPI, 'getLoggedIn')
           .returns(Promise.resolve(true));
       const data = {canonicalPath: ''};
       const redirectStub = sandbox.stub(element, '_redirectToLogin');
@@ -193,7 +193,7 @@
     });
 
     test('_redirectIfNotLoggedIn while logged out', () => {
-      sandbox.stub(element._restAPI, 'getLoggedIn')
+      sandbox.stub(element.$.restAPI, 'getLoggedIn')
           .returns(Promise.resolve(false));
       const redirectStub = sandbox.stub(element, '_redirectToLogin');
       const data = {canonicalPath: ''};
@@ -304,34 +304,51 @@
 
       setup(() => {
         projectLookupStub = sandbox
-            .stub(element._restAPI, 'getFromProjectLookup')
-            .returns(Promise.resolve('foo/bar'));
+            .stub(element.$.restAPI, 'getFromProjectLookup');
         sandbox.stub(element, '_generateUrl');
       });
 
       suite('_normalizeLegacyRouteParams', () => {
         let rangeStub;
+        let redirectStub;
 
         setup(() => {
           rangeStub = sandbox.stub(element, '_normalizePatchRangeParams')
               .returns(Promise.resolve());
+          redirectStub = sandbox.stub(element, '_redirect');
         });
 
         test('w/o changeNum', () => {
+          projectLookupStub.returns(Promise.resolve('foo/bar'));
           const params = {};
           return element._normalizeLegacyRouteParams(params).then(() => {
             assert.isFalse(projectLookupStub.called);
             assert.isFalse(rangeStub.called);
             assert.isNotOk(params.project);
+            assert.isFalse(redirectStub.called);
           });
         });
 
         test('w/ changeNum', () => {
+          projectLookupStub.returns(Promise.resolve('foo/bar'));
           const params = {changeNum: 1234};
           return element._normalizeLegacyRouteParams(params).then(() => {
             assert.isTrue(projectLookupStub.called);
             assert.isTrue(rangeStub.called);
             assert.equal(params.project, 'foo/bar');
+            assert.isTrue(redirectStub.calledOnce);
+          });
+        });
+
+        test('halts on project lookup failure', () => {
+          projectLookupStub.returns(Promise.resolve(undefined));
+
+          const params = {changeNum: 1234};
+          return element._normalizeLegacyRouteParams(params).then(() => {
+            assert.isTrue(projectLookupStub.called);
+            assert.isFalse(rangeStub.called);
+            assert.isUndefined(params.project);
+            assert.isFalse(redirectStub.called);
           });
         });
       });
@@ -472,7 +489,7 @@
         });
 
         test('redirects to dahsboard if logged in', () => {
-          sandbox.stub(element._restAPI, 'getLoggedIn')
+          sandbox.stub(element.$.restAPI, 'getLoggedIn')
               .returns(Promise.resolve(true));
           const data = {
             canonicalPath: '/', path: '/', querystring: '', hash: '',
@@ -485,7 +502,7 @@
         });
 
         test('redirects to open changes if not logged in', () => {
-          sandbox.stub(element._restAPI, 'getLoggedIn')
+          sandbox.stub(element.$.restAPI, 'getLoggedIn')
               .returns(Promise.resolve(false));
           const data = {
             canonicalPath: '/', path: '/', querystring: '', hash: '',
@@ -592,7 +609,7 @@
         });
 
         test('own dahsboard but signed out redirects to login', () => {
-          sandbox.stub(element._restAPI, 'getLoggedIn')
+          sandbox.stub(element.$.restAPI, 'getLoggedIn')
               .returns(Promise.resolve(false));
           const data = {canonicalPath: '/dashboard', params: {0: 'seLF'}};
           const result = element._handleDashboardRoute(data);
@@ -605,7 +622,7 @@
         });
 
         test('non-self dahsboard but signed out does not redirect', () => {
-          sandbox.stub(element._restAPI, 'getLoggedIn')
+          sandbox.stub(element.$.restAPI, 'getLoggedIn')
               .returns(Promise.resolve(false));
           const data = {canonicalPath: '/dashboard', params: {0: 'foo'}};
           const result = element._handleDashboardRoute(data);
@@ -619,7 +636,7 @@
         });
 
         test('dahsboard while signed in sets params', () => {
-          sandbox.stub(element._restAPI, 'getLoggedIn')
+          sandbox.stub(element.$.restAPI, 'getLoggedIn')
               .returns(Promise.resolve(true));
           const data = {canonicalPath: '/dashboard', params: {0: 'foo'}};
           const result = element._handleDashboardRoute(data);
@@ -1051,7 +1068,7 @@
           setup(() => {
             normalizeRangeStub = sandbox.stub(element,
                 '_normalizePatchRangeParams');
-            sandbox.stub(element._restAPI, 'setInProjectLookup');
+            sandbox.stub(element.$.restAPI, 'setInProjectLookup');
           });
 
           test('needs redirect', () => {
@@ -1103,7 +1120,7 @@
         test('_handleDiffEditRoute', () => {
           const normalizeRangeStub =
               sandbox.stub(element, '_normalizePatchRangeParams');
-          sandbox.stub(element._restAPI, 'setInProjectLookup');
+          sandbox.stub(element.$.restAPI, 'setInProjectLookup');
           const ctx = {
             params: [
               'foo/bar', // 0 Project
diff --git a/polygerrit-ui/app/elements/shared/gr-rest-api-interface/gr-rest-api-interface.js b/polygerrit-ui/app/elements/shared/gr-rest-api-interface/gr-rest-api-interface.js
index 210c42f..a016037 100644
--- a/polygerrit-ui/app/elements/shared/gr-rest-api-interface/gr-rest-api-interface.js
+++ b/polygerrit-ui/app/elements/shared/gr-rest-api-interface/gr-rest-api-interface.js
@@ -1811,7 +1811,13 @@
     getFromProjectLookup(changeNum) {
       const project = this._projectLookup[changeNum];
       if (project) { return Promise.resolve(project); }
-      return this.getChange(changeNum).then(change => {
+
+      const onError = response => {
+        // Fire a page error so that the visual 404 is displayed.
+        this.fire('page-error', {response});
+      };
+
+      return this.getChange(changeNum, onError).then(change => {
         if (!change || !change.project) { return; }
         this.setInProjectLookup(changeNum, change.project);
         return change.project;
@@ -1842,7 +1848,7 @@
 
    /**
     * Alias for _changeBaseURL.then(fetchJSON).
-     * @todo(beckysiegel) clean up comments
+    * @todo(beckysiegel) clean up comments
     * @param {string|number} changeNum
     * @param {string} endpoint
     * @param {?string|number=} opt_patchNum gets passed as null.
diff --git a/polygerrit-ui/app/elements/shared/gr-rest-api-interface/gr-rest-api-interface_test.html b/polygerrit-ui/app/elements/shared/gr-rest-api-interface/gr-rest-api-interface_test.html
index 2058f59..3f47ea8 100644
--- a/polygerrit-ui/app/elements/shared/gr-rest-api-interface/gr-rest-api-interface_test.html
+++ b/polygerrit-ui/app/elements/shared/gr-rest-api-interface/gr-rest-api-interface_test.html
@@ -865,8 +865,7 @@
       });
 
       test('getChange succeeds, no project', () => {
-        sandbox.stub(element, 'getChange')
-            .returns(Promise.resolve({}));
+        sandbox.stub(element, 'getChange').returns(Promise.resolve());
         return element.getFromProjectLookup().then(val => {
           assert.strictEqual(val, undefined);
           assert.deepEqual(element._projectLookup, {});