--- a/taskcluster/taskgraph/transforms/docker_image.py
+++ b/taskcluster/taskgraph/transforms/docker_image.py
@@ -58,27 +58,31 @@ docker_image_schema = Schema({
 def validate(config, tasks):
     for task in tasks:
         validate_schema(
             docker_image_schema, task,
             "In docker image {!r}:".format(task.get('name', 'unknown')))
         yield task
 
 
-def order_image_tasks(tasks):
+def order_image_tasks(config, tasks):
     """Iterate image tasks in an order where parent images come first."""
     pending = deque(tasks)
+    task_names = {task['name'] for task in pending}
     emitted = set()
     while True:
         try:
             task = pending.popleft()
         except IndexError:
             break
         parent = task.get('parent')
         if parent and parent not in emitted:
+            if parent not in task_names:
+                raise Exception('Missing parant image for {}-{}: {}'.format(
+                    config.kind, task['name'], parent))
             pending.append(task)
             continue
         emitted.add(task['name'])
         yield task
 
 
 @transforms.add
 def fill_template(config, tasks):
@@ -92,17 +96,17 @@ def fill_template(config, tasks):
                 # Only keep the hash part of the route.
                 h = route.rsplit('.', 1)[1]
                 assert DIGEST_RE.match(h)
                 available_packages[name] = h
                 break
 
     context_hashes = {}
 
-    for task in order_image_tasks(tasks):
+    for task in order_image_tasks(config, tasks):
         image_name = task.pop('name')
         job_symbol = task.pop('symbol')
         args = task.pop('args', {})
         definition = task.pop('definition', image_name)
         packages = task.pop('packages', [])
         parent = task.pop('parent', None)
 
         for p in packages: