diff --git a/tempest/scenario/test_network_advanced_server_ops.py b/tempest/scenario/test_network_advanced_server_ops.py
index 431de9a..2850b1b 100644
--- a/tempest/scenario/test_network_advanced_server_ops.py
+++ b/tempest/scenario/test_network_advanced_server_ops.py
@@ -73,6 +73,9 @@
                                          create_kwargs=create_kwargs)
         self.floating_ip = self._create_floating_ip(self.server,
                                                     public_network_id)
+        # Verify that we can indeed connect to the server before we mess with
+        # it's state
+        self._wait_server_status_and_check_network_connectivity()
 
     def _check_network_connectivity(self, should_connect=True):
         username = CONF.compute.image_ssh_user