diff --git a/designate_tempest_plugin/clients.py b/designate_tempest_plugin/clients.py
index 6ad397f..17df788 100644
--- a/designate_tempest_plugin/clients.py
+++ b/designate_tempest_plugin/clients.py
@@ -36,6 +36,8 @@
     PoolClient
 from designate_tempest_plugin.services.dns.v2.json.tld_client import \
     TldClient
+from designate_tempest_plugin.services.dns.query.query_client import \
+    QueryClient
 
 CONF = config.CONF
 
@@ -84,3 +86,9 @@
                                       **params)
         self.tld_client = TldClient(self.auth_provider,
                                     **params)
+        self.query_client = QueryClient(
+            nameservers=CONF.dns.nameservers,
+            query_timeout=CONF.dns.query_timeout,
+            build_interval=CONF.dns.build_interval,
+            build_timeout=CONF.dns.build_timeout,
+        )
diff --git a/designate_tempest_plugin/common/waiters.py b/designate_tempest_plugin/common/waiters.py
index dbdbd5a..efd3625 100644
--- a/designate_tempest_plugin/common/waiters.py
+++ b/designate_tempest_plugin/common/waiters.py
@@ -147,4 +147,49 @@
             if caller:
                 message = '(%s) %s' % (caller, message)
 
-            raise lib_exc.TimeoutException(message)
\ No newline at end of file
+            raise lib_exc.TimeoutException(message)
+
+
+def wait_for_query(client, name, rdatatype, found=True):
+    """Query nameservers until the record of the given name and type is found.
+
+    :param client: A QueryClient
+    :param name: The record name for which to query
+    :param rdatatype: The record type for which to query
+    :param found: If True, wait until the record is found. Else, wait until the
+        record disappears.
+    """
+    state = "found" if found else "removed"
+    LOG.info("Waiting for record %s of type %s to be %s on nameservers %s",
+             name, rdatatype, state, client.nameservers)
+    start = int(time.time())
+
+    while True:
+        time.sleep(client.build_interval)
+
+        responses = client.query(name, rdatatype)
+        if found:
+            all_answers_good = all(r.answer for r in responses)
+        else:
+            all_answers_good = all(not r.answer for r in responses)
+
+        if not client.nameservers or all_answers_good:
+            LOG.info("Record %s of type %s was successfully %s on nameservers "
+                     "%s", name, rdatatype, state, client.nameservers)
+            return
+
+        if int(time.time()) - start >= client.build_timeout:
+            message = ('Record %(name)s of type %(rdatatype)s not %(state)s '
+                       'on nameservers %(nameservers)s within the required '
+                       'time (%(timeout)s s)' %
+                       {'name': name,
+                        'rdatatype': rdatatype,
+                        'state': state,
+                        'nameservers': client.nameservers,
+                        'timeout': client.build_timeout})
+
+            caller = misc_utils.find_test_caller()
+            if caller:
+                message = "(%s) %s" % (caller, message)
+
+            raise lib_exc.TimeoutException(message)
diff --git a/designate_tempest_plugin/config.py b/designate_tempest_plugin/config.py
index 611d90f..c1dc79f 100644
--- a/designate_tempest_plugin/config.py
+++ b/designate_tempest_plugin/config.py
@@ -43,6 +43,12 @@
     cfg.IntOpt('min_ttl',
                default=1,
                help="The minimum value to respect when generating ttls"),
+    cfg.ListOpt('nameservers',
+                default=[],
+                help="The nameservers to check for change going live"),
+    cfg.IntOpt('query_timeout',
+               default=1,
+               help="The timeout on a single dns query to a nameserver"),
 
 ]
 
diff --git a/designate_tempest_plugin/services/dns/query/__init__.py b/designate_tempest_plugin/services/dns/query/__init__.py
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/designate_tempest_plugin/services/dns/query/__init__.py
diff --git a/designate_tempest_plugin/services/dns/query/query_client.py b/designate_tempest_plugin/services/dns/query/query_client.py
new file mode 100644
index 0000000..c4df36a
--- /dev/null
+++ b/designate_tempest_plugin/services/dns/query/query_client.py
@@ -0,0 +1,82 @@
+# Copyright 2016 Rackspace
+#
+# 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 dns
+import dns.exception
+import dns.query
+from tempest import config
+
+CONF = config.CONF
+
+
+class QueryClient(object):
+    """A client which queries multiple nameservers"""
+
+    def __init__(self, nameservers=None, query_timeout=None,
+                 build_interval=None, build_timeout=None):
+        self.nameservers = nameservers or []
+        self.query_timeout = query_timeout or CONF.dns.query_timeout
+        self.build_interval = build_interval or CONF.dns.build_interval
+        self.build_timeout = build_timeout or CONF.dns.build_timeout
+
+        self.clients = [SingleQueryClient(ns, query_timeout=query_timeout)
+                        for ns in nameservers]
+
+    def query(self, zone_name, rdatatype):
+        return [c.query(zone_name, rdatatype) for c in self.clients]
+
+
+class SingleQueryClient(object):
+    """A client which queries a single nameserver"""
+
+    def __init__(self, nameserver, query_timeout):
+        self.nameserver = Nameserver(nameserver)
+        self.query_timeout = query_timeout
+
+    def query(self, name, rdatatype):
+        return self._dig(name, rdatatype, self.nameserver.ip,
+                         self.nameserver.port, timeout=self.query_timeout)
+
+    @classmethod
+    def _prepare_query(cls, zone_name, rdatatype):
+        # support plain strings: "SOA", "A"
+        if isinstance(rdatatype, basestring):
+            rdatatype = dns.rdatatype.from_text(rdatatype)
+        dns_message = dns.message.make_query(zone_name, rdatatype)
+        dns_message.set_opcode(dns.opcode.QUERY)
+        return dns_message
+
+    @classmethod
+    def _dig(cls, name, rdatatype, ip, port, timeout):
+        query = cls._prepare_query(name, rdatatype)
+        return dns.query.udp(query, ip, port=port, timeout=timeout)
+
+
+class Nameserver(object):
+
+    def __init__(self, ip, port=53):
+        self.ip = ip
+        self.port = port
+
+    def __str__(self):
+        return "%s:%s" % (self.ip, self.port)
+
+    def __repr__(self):
+        return str(self)
+
+    @classmethod
+    def from_str(self, nameserver):
+        if ':' in nameserver:
+            ip, port = nameserver.split(':')
+            return Nameserver(ip, int(port))
+        return Nameserver(nameserver)
diff --git a/designate_tempest_plugin/tests/scenario/v2/test_zones.py b/designate_tempest_plugin/tests/scenario/v2/test_zones.py
index afd5b40..6ee479f 100644
--- a/designate_tempest_plugin/tests/scenario/v2/test_zones.py
+++ b/designate_tempest_plugin/tests/scenario/v2/test_zones.py
@@ -27,6 +27,7 @@
         super(ZonesTest, cls).setup_clients()
 
         cls.client = cls.os.zones_client
+        cls.query_client = cls.os.query_client
 
     @test.attr(type='slow')
     @test.idempotent_id('d0648f53-4114-45bd-8792-462a82f69d32')
@@ -80,3 +81,31 @@
         self.assertEqual('PENDING', zone['status'])
 
         waiters.wait_for_zone_404(self.client, zone['id'])
+
+    @test.attr(type='slow')
+    @test.idempotent_id('ad8d1f5b-da66-46a0-bbee-14dc84a5d791')
+    def test_zone_create_propagates_to_nameservers(self):
+        LOG.info('Create a zone')
+        _, zone = self.client.create_zone()
+        self.addCleanup(self.client.delete_zone, zone['id'])
+
+        waiters.wait_for_zone_status(self.client, zone['id'], "ACTIVE")
+        waiters.wait_for_query(self.query_client, zone['name'], "SOA")
+
+    @test.attr(type='slow')
+    @test.idempotent_id('d13d3095-c78f-4aae-8fe3-a74ccc335c84')
+    def test_zone_delete_propagates_to_nameservers(self):
+        LOG.info('Create a zone')
+        _, zone = self.client.create_zone()
+        self.addCleanup(self.client.delete_zone, zone['id'],
+                        ignore_errors=lib_exc.NotFound)
+
+        waiters.wait_for_zone_status(self.client, zone['id'], "ACTIVE")
+        waiters.wait_for_query(self.query_client, zone['name'], "SOA")
+
+        LOG.info('Delete the zone')
+        self.client.delete_zone(zone['id'])
+
+        waiters.wait_for_zone_404(self.client, zone['id'])
+        waiters.wait_for_query(self.query_client, zone['name'], "SOA",
+                               found=False)
diff --git a/requirements.txt b/requirements.txt
index b6c32bd..d9368e0 100644
--- a/requirements.txt
+++ b/requirements.txt
@@ -2,4 +2,6 @@
 # of appearance. Changing the order has an impact on the overall integration
 # process, which may cause wedges in the gate later.
 
+dnspython>=1.12.0,!=1.13.0;python_version<'3.0'  # http://www.dnspython.org/LICENSE
+dnspython3>=1.12.0;python_version>='3.0'  # http://www.dnspython.org/LICENSE
 tempest>=11.0.0 # Apache-2.0