diff --git a/swh/scheduler/celery_backend/config.py b/swh/scheduler/celery_backend/config.py
--- a/swh/scheduler/celery_backend/config.py
+++ b/swh/scheduler/celery_backend/config.py
@@ -122,6 +122,8 @@
         )
         credentials = (conn_info['userid'], conn_info['password'])
         r = requests.get(url, auth=credentials)
+        if r.status_code == 404:
+            return {}
         if r.status_code != 200:
             raise ValueError('Got error %s when reading queue stats: %s' % (
                 r.status_code, r.json()))
@@ -131,7 +133,7 @@
         """Shortcut to get a queue's length"""
         stats = self.get_queue_stats(queue_name)
         if stats:
-            return stats['messages']
+            return stats.get('messages')
 
 
 INSTANCE_NAME = os.environ.get(CONFIG_NAME_ENVVAR)
diff --git a/swh/scheduler/celery_backend/runner.py b/swh/scheduler/celery_backend/runner.py
--- a/swh/scheduler/celery_backend/runner.py
+++ b/swh/scheduler/celery_backend/runner.py
@@ -49,7 +49,11 @@
             backend_name = task_type['backend_name']
             if max_queue_length and backend_name in app.tasks:
                 queue_name = app.tasks[backend_name].task_queue
-                queue_length = app.get_queue_length(queue_name)
+                try:
+                    queue_length = app.get_queue_length(queue_name)
+                except ValueError:
+                    queue_length = None
+
                 if queue_length is None:
                     # Running without RabbitMQ (probably a test env).
                     num_tasks = MAX_NUM_TASKS