diff --git a/cypress/integration/origin-search.spec.js b/cypress/integration/origin-search.spec.js
--- a/cypress/integration/origin-search.spec.js
+++ b/cypress/integration/origin-search.spec.js
@@ -89,6 +89,209 @@
       });
   });
 
+  context('Test pagination', function() {
+    it('should not paginate if there are not many results', function() {
+      // Setup search
+      cy.get('#swh-search-origins-with-visit')
+        .uncheck()
+        .get('#swh-filter-empty-visits')
+        .uncheck()
+        .then(() => {
+          const searchText = 'libtess';
+
+          // Get first page of results
+          doSearch(searchText);
+
+          cy.get('.swh-search-result-entry')
+            .should('have.length', 1);
+
+          cy.get('.swh-search-result-entry#origin-0 td a')
+            .should('have.text', 'https://github.com/memononen/libtess2');
+
+          cy.get('#origins-prev-results-button')
+            .should('have.class', 'disabled');
+          cy.get('#origins-next-results-button')
+            .should('have.class', 'disabled');
+        });
+    });
+
+    it('should paginate forward when there are many results', function() {
+      // Setup search
+      cy.get('#swh-search-origins-with-visit')
+        .uncheck()
+        .get('#swh-filter-empty-visits')
+        .uncheck()
+        .then(() => {
+          const searchText = 'many.origins';
+
+          // Get first page of results
+          doSearch(searchText);
+
+          cy.get('.swh-search-result-entry')
+            .should('have.length', 100);
+
+          cy.get('.swh-search-result-entry#origin-0 td a')
+            .should('have.text', 'https://many.origins/1');
+          cy.get('.swh-search-result-entry#origin-99 td a')
+            .should('have.text', 'https://many.origins/100');
+
+          cy.get('#origins-prev-results-button')
+            .should('have.class', 'disabled');
+          cy.get('#origins-next-results-button')
+            .should('not.have.class', 'disabled');
+
+          // Get second page of results
+          cy.get('#origins-next-results-button a')
+            .click();
+
+          cy.get('.swh-search-result-entry')
+            .should('have.length', 100);
+
+          cy.get('.swh-search-result-entry#origin-0 td a')
+            .should('have.text', 'https://many.origins/101');
+          cy.get('.swh-search-result-entry#origin-99 td a')
+            .should('have.text', 'https://many.origins/200');
+
+          cy.get('#origins-prev-results-button')
+            .should('not.have.class', 'disabled');
+          cy.get('#origins-next-results-button')
+            .should('not.have.class', 'disabled');
+
+          // Get third (and last) page of results
+          cy.get('#origins-next-results-button a')
+            .click();
+
+          cy.get('.swh-search-result-entry')
+            .should('have.length', 50);
+
+          cy.get('.swh-search-result-entry#origin-0 td a')
+            .should('have.text', 'https://many.origins/201');
+          cy.get('.swh-search-result-entry#origin-49 td a')
+            .should('have.text', 'https://many.origins/250');
+
+          cy.get('#origins-prev-results-button')
+            .should('not.have.class', 'disabled');
+          cy.get('#origins-next-results-button')
+            .should('have.class', 'disabled');
+        });
+    });
+
+    it('should paginate backward from a middle page', function() {
+      // Setup search
+      cy.get('#swh-search-origins-with-visit')
+        .uncheck()
+        .get('#swh-filter-empty-visits')
+        .uncheck()
+        .then(() => {
+          const searchText = 'many.origins';
+
+          // Get first page of results
+          doSearch(searchText);
+
+          cy.get('#origins-prev-results-button')
+            .should('have.class', 'disabled');
+          cy.get('#origins-next-results-button')
+            .should('not.have.class', 'disabled');
+
+          // Get second page of results
+          cy.get('#origins-next-results-button a')
+            .click();
+          cy.get('#origins-prev-results-button')
+            .should('not.have.class', 'disabled');
+          cy.get('#origins-next-results-button')
+            .should('not.have.class', 'disabled');
+
+          // Get first page of results again
+          cy.get('#origins-prev-results-button a')
+            .click();
+
+          cy.get('.swh-search-result-entry')
+            .should('have.length', 100);
+
+          cy.get('.swh-search-result-entry#origin-0 td a')
+            .should('have.text', 'https://many.origins/1');
+          cy.get('.swh-search-result-entry#origin-99 td a')
+            .should('have.text', 'https://many.origins/100');
+
+          cy.get('#origins-prev-results-button')
+            .should('have.class', 'disabled');
+          cy.get('#origins-next-results-button')
+            .should('not.have.class', 'disabled');
+        });
+    });
+
+    it('should paginate backward from the last page', function() {
+      // Setup search
+      cy.get('#swh-search-origins-with-visit')
+        .uncheck()
+        .get('#swh-filter-empty-visits')
+        .uncheck()
+        .then(() => {
+          const searchText = 'many.origins';
+
+          // Get first page of results
+          doSearch(searchText);
+
+          cy.get('#origins-prev-results-button')
+            .should('have.class', 'disabled');
+          cy.get('#origins-next-results-button')
+            .should('not.have.class', 'disabled');
+
+          // Get second page of results
+          cy.get('#origins-next-results-button a')
+            .click();
+
+          cy.get('#origins-prev-results-button')
+            .should('not.have.class', 'disabled');
+          cy.get('#origins-next-results-button')
+            .should('not.have.class', 'disabled');
+
+          // Get third (and last) page of results
+          cy.get('#origins-next-results-button a')
+            .click();
+
+          cy.get('#origins-prev-results-button')
+            .should('not.have.class', 'disabled');
+          cy.get('#origins-next-results-button')
+            .should('have.class', 'disabled');
+
+          // Get second page of results again
+          cy.get('#origins-prev-results-button a')
+            .click();
+
+          cy.get('.swh-search-result-entry')
+            .should('have.length', 100);
+
+          cy.get('.swh-search-result-entry#origin-0 td a')
+            .should('have.text', 'https://many.origins/101');
+          cy.get('.swh-search-result-entry#origin-99 td a')
+            .should('have.text', 'https://many.origins/200');
+
+          cy.get('#origins-prev-results-button')
+            .should('not.have.class', 'disabled');
+          cy.get('#origins-next-results-button')
+            .should('not.have.class', 'disabled');
+
+          // Get first page of results again
+          cy.get('#origins-prev-results-button a')
+            .click();
+
+          cy.get('.swh-search-result-entry')
+            .should('have.length', 100);
+
+          cy.get('.swh-search-result-entry#origin-0 td a')
+            .should('have.text', 'https://many.origins/1');
+          cy.get('.swh-search-result-entry#origin-99 td a')
+            .should('have.text', 'https://many.origins/100');
+
+          cy.get('#origins-prev-results-button')
+            .should('have.class', 'disabled');
+          cy.get('#origins-next-results-button')
+            .should('not.have.class', 'disabled');
+        });
+    });
+  });
+
   context('Test valid persistent ids', function() {
     it('should resolve directory', function() {
       const redirectUrl = this.Urls.browse_directory(origin.content[0].directory);
diff --git a/swh/web/assets/src/bundles/browse/origin-search.js b/swh/web/assets/src/bundles/browse/origin-search.js
--- a/swh/web/assets/src/bundles/browse/origin-search.js
+++ b/swh/web/assets/src/bundles/browse/origin-search.js
@@ -8,13 +8,17 @@
 import {heapsPermute} from 'utils/heaps-permute';
 import {handleFetchError} from 'utils/functions';
 
-let originPatterns;
-let perPage = 100;
-let limit = perPage * 2;
-let offset = 0;
-let currentData = null;
+const limit = 100;
+let linksPrev = [];
+let linkNext = null;
+let linkCurrent = null;
 let inSearch = false;
 
+function parseLinkHeader(s) {
+  let re = /<(.+)>; rel="next"/;
+  return s.match(re)[1];
+}
+
 function fixTableRowsStyle() {
   setTimeout(() => {
     $('#origin-search-results tbody tr').removeAttr('style');
@@ -25,15 +29,13 @@
   $('#origin-search-results tbody tr').remove();
 }
 
-function populateOriginSearchResultsTable(origins, offset) {
-  let localOffset = offset % limit;
+function populateOriginSearchResultsTable(origins) {
   if (origins.length > 0) {
     $('#swh-origin-search-results').show();
     $('#swh-no-result').hide();
     clearOriginSearchResultsTable();
     let table = $('#origin-search-results tbody');
-    for (let i = localOffset; i < localOffset + perPage && i < origins.length; ++i) {
-      let origin = origins[i];
+    for (let [i, origin] of origins.entries()) {
       let browseUrl = Urls.browse_origin(origin.url);
       let tableRow = `<tr id="origin-${i}" class="swh-search-result-entry swh-tr-hover-highlight">`;
       tableRow += `<td style="white-space: nowrap;"><a href="${encodeURI(browseUrl)}">${encodeURI(origin.url)}</a></td>`;
@@ -65,17 +67,19 @@
     $('#swh-no-result').text('No origins matching the search criteria were found.');
     $('#swh-no-result').show();
   }
-  if (origins.length - localOffset < perPage ||
-      (origins.length < limit && (localOffset + perPage) === origins.length)) {
+
+  if (linkNext === null) {
     $('#origins-next-results-button').addClass('disabled');
   } else {
     $('#origins-next-results-button').removeClass('disabled');
   }
-  if (offset > 0) {
-    $('#origins-prev-results-button').removeClass('disabled');
-  } else {
+
+  if (linksPrev.length === 0) {
     $('#origins-prev-results-button').addClass('disabled');
+  } else {
+    $('#origins-prev-results-button').removeClass('disabled');
   }
+
   inSearch = false;
   setTimeout(() => {
     window.scrollTo(0, 0);
@@ -87,13 +91,12 @@
   return str.replace(matchOperatorsRe, '%5C$&');
 }
 
-function searchOrigins(patterns, limit, searchOffset, offset) {
+function searchOriginsFirst(patterns, limit) {
   let baseSearchUrl;
   let searchMetadata = $('#swh-search-origin-metadata').prop('checked');
   if (searchMetadata) {
     baseSearchUrl = Urls.api_1_origin_metadata_search() + `?fulltext=${patterns}`;
   } else {
-    originPatterns = patterns;
     let patternsArray = patterns.trim().replace(/\s+/g, ' ').split(' ');
     for (let i = 0; i < patternsArray.length; ++i) {
       patternsArray[i] = escapeStringRegexp(patternsArray[i]);
@@ -111,17 +114,35 @@
   }
 
   let withVisit = $('#swh-search-origins-with-visit').prop('checked');
-  let searchUrl = baseSearchUrl + `&limit=${limit}&offset=${searchOffset}&with_visit=${withVisit}`;
+  let searchUrl = baseSearchUrl + `&limit=${limit}&with_visit=${withVisit}`;
+  searchOrigins(searchUrl);
+}
 
+function searchOrigins(searchUrl) {
   clearOriginSearchResultsTable();
   $('.swh-loading').addClass('show');
-  fetch(searchUrl)
+  let response = fetch(searchUrl)
     .then(handleFetchError)
-    .then(response => response.json())
+    .then(resp => {
+      response = resp;
+      return response.json();
+    })
     .then(data => {
-      currentData = data;
+      // Save link to the current results page
+      linkCurrent = searchUrl;
+      // Save link to the next results page.
+      linkNext = null;
+      if (response.headers.has('Link')) {
+        let parsedLink = parseLinkHeader(response.headers.get('Link'));
+        if (parsedLink !== undefined) {
+          linkNext = parsedLink;
+        }
+      }
+      // prevLinks is updated by the caller, which is the one to know if
+      // we're going forward or backward in the pages.
+
       $('.swh-loading').removeClass('show');
-      populateOriginSearchResultsTable(data, offset);
+      populateOriginSearchResultsTable(data);
     })
     .catch(response => {
       $('.swh-loading').removeClass('show');
@@ -135,7 +156,6 @@
 function doSearch() {
   $('#swh-no-result').hide();
   let patterns = $('#origins-url-patterns').val();
-  offset = 0;
   inSearch = true;
   // first try to resolve a swh persistent identifier
   let resolvePidUrl = Urls.api_1_resolve_swh_pid(patterns);
@@ -162,7 +182,7 @@
         // otherwise, proceed with origins search
         $('#swh-origin-search-results').show();
         $('.swh-search-pagination').show();
-        searchOrigins(patterns, limit, offset, offset);
+        searchOriginsFirst(patterns, limit);
       }
     });
 }
@@ -194,12 +214,8 @@
         return;
       }
       inSearch = true;
-      offset += perPage;
-      if (!currentData || (offset >= limit && offset % limit === 0)) {
-        searchOrigins(originPatterns, limit, offset, offset);
-      } else {
-        populateOriginSearchResultsTable(currentData, offset);
-      }
+      linksPrev.push(linkCurrent);
+      searchOrigins(linkNext);
       event.preventDefault();
     });
 
@@ -208,12 +224,7 @@
         return;
       }
       inSearch = true;
-      offset -= perPage;
-      if (!currentData || (offset > 0 && (offset + perPage) % limit === 0)) {
-        searchOrigins(originPatterns, limit, (offset + perPage) - limit, offset);
-      } else {
-        populateOriginSearchResultsTable(currentData, offset);
-      }
+      searchOrigins(linksPrev.pop());
       event.preventDefault();
     });
 
diff --git a/swh/web/tests/data.py b/swh/web/tests/data.py
--- a/swh/web/tests/data.py
+++ b/swh/web/tests/data.py
@@ -184,6 +184,11 @@
 
         origin.update(storage.origin_get(origin))  # add an 'id' key if enabled
 
+    for i in range(250):
+        url = 'https://many.origins/%d' % (i+1)
+        storage.origin_add([{'url': url}])
+        storage.origin_visit_add(url, '2019-12-03 13:55:05', 'tar')
+
     contents = set()
     directories = set()
     revisions = set()