diff --git a/test-requirements.txt b/test-requirements.txt
index c68b2db..d461078 100644
--- a/test-requirements.txt
+++ b/test-requirements.txt
@@ -11,3 +11,4 @@
 testrepository>=0.0.17
 testtools>=0.9.32
 sphinxcontrib-programoutput
+mock
diff --git a/tests/fixtures/gerrit/simple_query_pagination_new_1 b/tests/fixtures/gerrit/simple_query_pagination_new_1
new file mode 100644
index 0000000..b3fdd83
--- /dev/null
+++ b/tests/fixtures/gerrit/simple_query_pagination_new_1
@@ -0,0 +1,5 @@
+gerrit query --format json --commit-message --current-patch-set project:openstack-infra/zuul
+{"project":"openstack-infra/zuul","branch":"master","topic":"(detached","id":"I173251c8b1569755124b7cb1a48b6274bf38c94b","number":"202867","subject":"Report the per-job build wait time to graphite","owner":{"name":"Timothy R. Chavez","email":"timothy.chavez@hp.com","username":"timrchavez"},"url":"https://review.openstack.org/202867","commitMessage":"Report the per-job build wait time to graphite\n\nKnowing how long a job waits to build in aggregate can give useful\ninsights into the performance and capacity of the build system. This\nchange also uses the node labels sent back from the gearman worker to\nsubmit metrics within that context.\n\nChange-Id: I173251c8b1569755124b7cb1a48b6274bf38c94b\nDepends-On: Ibca938fcf8a65facd7e39dab4eb994dfc637722a\n","createdOn":1437104683,"lastUpdated":1440760891,"open":true,"status":"NEW"}
+{"project":"openstack-infra/zuul","branch":"master","topic":"ignore-deletes","id":"Iea75d05ddcb49b0bf748b72b9d2d5472d077f0c6","number":"178833","subject":"Add option to ignore ref-updated events emitted by branch deletions","owner":{"name":"K Jonathan Harker","email":"code@gentlydownthe.net","username":"jesusaurus"},"url":"https://review.openstack.org/178833","commitMessage":"Add option to ignore ref-updated events emitted by branch deletions\n\nWhen a branch is deleted, gerrit emits a ref-updated event with a newrev\nvalue of all zeros. This adds a boolean field to optionally not trigger\non these ref-updated events.\n\nChange-Id: Iea75d05ddcb49b0bf748b72b9d2d5472d077f0c6\n","createdOn":1430339761,"lastUpdated":1440735750,"open":true,"status":"NEW"}
+{"project":"openstack-infra/zuul","branch":"master","topic":"undefined-projects","id":"I7912197fb86c1a7becb7f43ca36078101f632715","number":"207094","subject":"Dependencies from undefined projects","owner":{"name":"Evgeny Antyshev","email":"eantyshev@virtuozzo.com","username":"eantyshev"},"url":"https://review.openstack.org/207094","commitMessage":"Dependencies from undefined projects\n\n3rd party CI layout usually has only a few projects defined,\nso it\u0027s possible that some changes depend on projects\nwhich are unknown to Zuul scheduler.\nThese items had None as a \"item.change.project\", which\nis not handled in many places, for ex. in reconfiguration.\n\nThese cases could be handled by defining these projects in layout\nas \"foreign\" projects: no jobs, no other non-standard attributes.\nChanges to those projects are also dropped, unless\nthey came as dependencies.\n\nChange-Id: I7912197fb86c1a7becb7f43ca36078101f632715\n","createdOn":1438183395,"lastUpdated":1440667433,"open":true,"status":"NEW"}
+{"type":"stats","rowCount":3,"runTimeMilliseconds":12,"moreChanges":true}
\ No newline at end of file
diff --git a/tests/fixtures/gerrit/simple_query_pagination_new_2 b/tests/fixtures/gerrit/simple_query_pagination_new_2
new file mode 100644
index 0000000..9fd8d54
--- /dev/null
+++ b/tests/fixtures/gerrit/simple_query_pagination_new_2
@@ -0,0 +1,4 @@
+gerrit query --format json --commit-message --current-patch-set project:openstack-infra/zuul -S 3
+{"project":"openstack-infra/zuul","branch":"master","topic":"github-integration","id":"I95f41088ea160d4e33a507c4a413e3fa7f08906b","number":"192457","subject":"(WIP) Fix job hierarchy bug.","owner":{"name":"Wayne Warren","email":"waynr+launchpad@sdf.org","username":"waynr"},"url":"https://review.openstack.org/192457","commitMessage":"(WIP) Fix job hierarchy bug.\n\nJobTree.addJob may return \u0027None\u0027, this prevents that from happening.\n\nChange-Id: I95f41088ea160d4e33a507c4a413e3fa7f08906b\n","createdOn":1434498278,"lastUpdated":1440608984,"sortKey":"003763050002efc9","open":true,"status":"NEW"}
+{"project":"openstack-infra/zuul","branch":"master","topic":"github-integration","id":"Ic5887d00ff302f67469df5154e9df10b99f1cfcd","number":"215642","subject":"(WIP) Allow using webapp from connections","owner":{"name":"Jan Hruban","email":"jan.hruban@gooddata.com","username":"hrubi"},"url":"https://review.openstack.org/215642","commitMessage":"(WIP) Allow using webapp from connections\n\nAllow connections to register their own handlers for HTTP URIs inside\nthe zuul\u0027s webapp HTTP server. That way, connections can listen for\nevents comming through HTTP.\n\nChange-Id: Ic5887d00ff302f67469df5154e9df10b99f1cfcd\n","createdOn":1440165019,"lastUpdated":1440602591,"sortKey":"0037629b00034a5a","open":true,"status":"NEW"}
+{"type":"stats","rowCount":2,"runTimeMilliseconds":12,"moreChanges":false}
\ No newline at end of file
diff --git a/tests/fixtures/gerrit/simple_query_pagination_old_1 b/tests/fixtures/gerrit/simple_query_pagination_old_1
new file mode 100644
index 0000000..8ff1710
--- /dev/null
+++ b/tests/fixtures/gerrit/simple_query_pagination_old_1
@@ -0,0 +1,5 @@
+gerrit query --format json --commit-message --current-patch-set project:openstack-infra/zuul
+{"project":"openstack-infra/zuul","branch":"master","topic":"(detached","id":"I173251c8b1569755124b7cb1a48b6274bf38c94b","number":"202867","subject":"Report the per-job build wait time to graphite","owner":{"name":"Timothy R. Chavez","email":"timothy.chavez@hp.com","username":"timrchavez"},"url":"https://review.openstack.org/202867","commitMessage":"Report the per-job build wait time to graphite\n\nKnowing how long a job waits to build in aggregate can give useful\ninsights into the performance and capacity of the build system. This\nchange also uses the node labels sent back from the gearman worker to\nsubmit metrics within that context.\n\nChange-Id: I173251c8b1569755124b7cb1a48b6274bf38c94b\nDepends-On: Ibca938fcf8a65facd7e39dab4eb994dfc637722a\n","createdOn":1437104683,"lastUpdated":1440760891,"sortKey":"00376ce900031873","open":true,"status":"NEW"}
+{"project":"openstack-infra/zuul","branch":"master","topic":"ignore-deletes","id":"Iea75d05ddcb49b0bf748b72b9d2d5472d077f0c6","number":"178833","subject":"Add option to ignore ref-updated events emitted by branch deletions","owner":{"name":"K Jonathan Harker","email":"code@gentlydownthe.net","username":"jesusaurus"},"url":"https://review.openstack.org/178833","commitMessage":"Add option to ignore ref-updated events emitted by branch deletions\n\nWhen a branch is deleted, gerrit emits a ref-updated event with a newrev\nvalue of all zeros. This adds a boolean field to optionally not trigger\non these ref-updated events.\n\nChange-Id: Iea75d05ddcb49b0bf748b72b9d2d5472d077f0c6\n","createdOn":1430339761,"lastUpdated":1440735750,"sortKey":"00376b460002ba91","open":true,"status":"NEW"}
+{"project":"openstack-infra/zuul","branch":"master","topic":"undefined-projects","id":"I7912197fb86c1a7becb7f43ca36078101f632715","number":"207094","subject":"Dependencies from undefined projects","owner":{"name":"Evgeny Antyshev","email":"eantyshev@virtuozzo.com","username":"eantyshev"},"url":"https://review.openstack.org/207094","commitMessage":"Dependencies from undefined projects\n\n3rd party CI layout usually has only a few projects defined,\nso it\u0027s possible that some changes depend on projects\nwhich are unknown to Zuul scheduler.\nThese items had None as a \"item.change.project\", which\nis not handled in many places, for ex. in reconfiguration.\n\nThese cases could be handled by defining these projects in layout\nas \"foreign\" projects: no jobs, no other non-standard attributes.\nChanges to those projects are also dropped, unless\nthey came as dependencies.\n\nChange-Id: I7912197fb86c1a7becb7f43ca36078101f632715\n","createdOn":1438183395,"lastUpdated":1440667433,"sortKey":"003766d3000328f6","open":true,"status":"NEW"}
+{"type":"stats","rowCount":3,"runTimeMilliseconds":12}
\ No newline at end of file
diff --git a/tests/fixtures/gerrit/simple_query_pagination_old_2 b/tests/fixtures/gerrit/simple_query_pagination_old_2
new file mode 100644
index 0000000..c55cd40
--- /dev/null
+++ b/tests/fixtures/gerrit/simple_query_pagination_old_2
@@ -0,0 +1,4 @@
+gerrit query --format json --commit-message --current-patch-set project:openstack-infra/zuul resume_sortkey:'003766d3000328f6'
+{"project":"openstack-infra/zuul","branch":"master","topic":"github-integration","id":"I95f41088ea160d4e33a507c4a413e3fa7f08906b","number":"192457","subject":"(WIP) Fix job hierarchy bug.","owner":{"name":"Wayne Warren","email":"waynr+launchpad@sdf.org","username":"waynr"},"url":"https://review.openstack.org/192457","commitMessage":"(WIP) Fix job hierarchy bug.\n\nJobTree.addJob may return \u0027None\u0027, this prevents that from happening.\n\nChange-Id: I95f41088ea160d4e33a507c4a413e3fa7f08906b\n","createdOn":1434498278,"lastUpdated":1440608984,"sortKey":"003763050002efc9","open":true,"status":"NEW"}
+{"project":"openstack-infra/zuul","branch":"master","topic":"github-integration","id":"Ic5887d00ff302f67469df5154e9df10b99f1cfcd","number":"215642","subject":"(WIP) Allow using webapp from connections","owner":{"name":"Jan Hruban","email":"jan.hruban@gooddata.com","username":"hrubi"},"url":"https://review.openstack.org/215642","commitMessage":"(WIP) Allow using webapp from connections\n\nAllow connections to register their own handlers for HTTP URIs inside\nthe zuul\u0027s webapp HTTP server. That way, connections can listen for\nevents comming through HTTP.\n\nChange-Id: Ic5887d00ff302f67469df5154e9df10b99f1cfcd\n","createdOn":1440165019,"lastUpdated":1440602591,"sortKey":"0037629b00034a5a","open":true,"status":"NEW"}
+{"type":"stats","rowCount":2,"runTimeMilliseconds":12}
\ No newline at end of file
diff --git a/tests/fixtures/gerrit/simple_query_pagination_old_3 b/tests/fixtures/gerrit/simple_query_pagination_old_3
new file mode 100644
index 0000000..b8cdc4a
--- /dev/null
+++ b/tests/fixtures/gerrit/simple_query_pagination_old_3
@@ -0,0 +1,2 @@
+gerrit query --format json --commit-message --current-patch-set project:openstack-infra/zuul resume_sortkey:'0037629b00034a5a'
+{"type":"stats","rowCount":0,"runTimeMilliseconds":12}
\ No newline at end of file
diff --git a/tests/test_gerrit.py b/tests/test_gerrit.py
new file mode 100644
index 0000000..dad2c6d
--- /dev/null
+++ b/tests/test_gerrit.py
@@ -0,0 +1,76 @@
+#!/usr/bin/env python
+
+# Copyright 2015 BMW Car IT GmbH
+#
+# Licensed under the Apache License, Version 2.0 (the "License"); you may
+# not use this file except in compliance with the License. You may obtain
+# a copy of the License at
+#
+#      http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+# License for the specific language governing permissions and limitations
+# under the License.
+import os
+
+try:
+    from unittest import mock
+except ImportError:
+    import mock
+
+from tests.base import BaseTestCase
+from zuul.lib.gerrit import Gerrit
+
+FIXTURE_DIR = os.path.join(os.path.dirname(__file__), 'fixtures/gerrit')
+
+
+def read_fixture(file):
+    with open('%s/%s' % (FIXTURE_DIR, file), 'r') as fixturefile:
+        lines = fixturefile.readlines()
+        command = lines[0].replace('\n', '')
+        value = ''.join(lines[1:])
+        return command, value
+
+
+def read_fixtures(files):
+    calls = []
+    values = []
+    for fixture_file in files:
+        command, value = read_fixture(fixture_file)
+        calls.append(mock.call(command))
+        values.append([value, ''])
+    return calls, values
+
+
+class TestGerrit(BaseTestCase):
+
+    @mock.patch('zuul.lib.gerrit.Gerrit._ssh')
+    def run_query(self, files, expected_patches, _ssh_mock):
+        gerrit = Gerrit('localhost', 'user')
+
+        calls, values = read_fixtures(files)
+        _ssh_mock.side_effect = values
+
+        result = gerrit.simpleQuery('project:openstack-infra/zuul')
+
+        _ssh_mock.assert_has_calls(calls)
+        self.assertEquals(len(calls), _ssh_mock.call_count,
+                          '_ssh should be called %d times' % len(calls))
+        self.assertIsNotNone(result, 'Result is not none')
+        self.assertEquals(len(result), expected_patches,
+                          'There must be %d patches.' % expected_patches)
+
+    def test_simple_query_pagination_new(self):
+        files = ['simple_query_pagination_new_1',
+                 'simple_query_pagination_new_2']
+        expected_patches = 5
+        self.run_query(files, expected_patches)
+
+    def test_simple_query_pagination_old(self):
+        files = ['simple_query_pagination_old_1',
+                 'simple_query_pagination_old_2',
+                 'simple_query_pagination_old_3']
+        expected_patches = 5
+        self.run_query(files, expected_patches)
diff --git a/zuul/lib/gerrit.py b/zuul/lib/gerrit.py
index 5889ed0..1434389 100644
--- a/zuul/lib/gerrit.py
+++ b/zuul/lib/gerrit.py
@@ -156,22 +156,42 @@
             lines = out.split('\n')
             if not lines:
                 return False
+
+            # filter out blank lines
             data = [json.loads(line) for line in lines
-                    if "sortKey" in line]
+                    if line.startswith('{')]
+
+            # check last entry for more changes
+            more_changes = None
+            if 'moreChanges' in data[-1]:
+                more_changes = data[-1]['moreChanges']
+
+            # we have to remove the statistics line
+            del data[-1]
+
             if not data:
-                return False
+                return False, more_changes
             self.log.debug("Received data from Gerrit query: \n%s" %
                            (pprint.pformat(data)))
-            return data
+            return data, more_changes
 
         # gerrit returns 500 results by default, so implement paging
         # for large projects like nova
         alldata = []
-        chunk = _query_chunk(query)
+        chunk, more_changes = _query_chunk(query)
         while(chunk):
             alldata.extend(chunk)
-            sortkey = "resume_sortkey:'%s'" % chunk[-1]["sortKey"]
-            chunk = _query_chunk("%s %s" % (query, sortkey))
+            if more_changes is None:
+                # continue sortKey based (before Gerrit 2.9)
+                resume = "resume_sortkey:'%s'" % chunk[-1]["sortKey"]
+            elif more_changes:
+                # continue moreChanges based (since Gerrit 2.9)
+                resume = "-S %d" % len(alldata)
+            else:
+                # no more changes
+                break
+
+            chunk, more_changes = _query_chunk("%s %s" % (query, resume))
         return alldata
 
     def _open(self):