--- a/taskcluster/taskgraph/create.py
+++ b/taskcluster/taskgraph/create.py
@@ -2,31 +2,41 @@
 # License, v. 2.0. If a copy of the MPL was not distributed with this
 # file, You can obtain one at http://mozilla.org/MPL/2.0/.
 
 from __future__ import absolute_import, print_function, unicode_literals
 
 import requests
 import json
 import collections
+import os
 import logging
 
 from slugid import nice as slugid
 
 logger = logging.getLogger(__name__)
 
 def create_tasks(taskgraph, label_to_taskid):
     # TODO: use the taskGroupId of the decision task
     task_group_id = slugid()
     taskid_to_label = {t: l for l, t in label_to_taskid.iteritems()}
 
     session = requests.Session()
 
+    decision_task_id = os.environ.get('TASK_ID')
+
     for task_id in taskgraph.graph.visit_postorder():
         task_def = taskgraph.tasks[task_id].task
+
+        # if this task has no dependencies, make it depend on this decision
+        # task so that it does not start immediately; and so that if this loop
+        # fails halfway through, none of the already-created tasks run.
+        if decision_task_id and not task_def.get('dependencies'):
+            task_def['dependencies'] = [decision_task_id]
+
         task_def['taskGroupId'] = task_group_id
         _create_task(session, task_id, taskid_to_label[task_id], task_def)
 
 def _create_task(session, task_id, label, task_def):
     # create the task using 'http://taskcluster/queue', which is proxied to the queue service
     # with credentials appropriate to this job.
     logger.debug("Creating task with taskId {} for {}".format(task_id, label))
     res = session.put('http://taskcluster/queue/v1/task/{}'.format(task_id), data=json.dumps(task_def))

--- a/taskcluster/taskgraph/test/test_create.py
+++ b/taskcluster/taskgraph/test/test_create.py
@@ -1,15 +1,16 @@
 # This Source Code Form is subject to the terms of the Mozilla Public
 # License, v. 2.0. If a copy of the MPL was not distributed with this
 # file, You can obtain one at http://mozilla.org/MPL/2.0/.
 
 from __future__ import absolute_import, print_function, unicode_literals
 
 import unittest
+import os
 
 from .. import create
 from ..graph import Graph
 from ..types import Task, TaskGraph
 
 from mozunit import main
 
 class FakeKind(object):
@@ -19,22 +20,29 @@ class FakeKind(object):
         for k, v in deps_by_name.iteritems():
             assert k == 'edge'
         return {'payload': 'hello world'}
 
 
 class TestCreate(unittest.TestCase):
 
     def setUp(self):
+        self.old_task_id = os.environ.get('TASK_ID')
+        if 'TASK_ID' in os.environ:
+            del os.environ['TASK_ID']
         self.created_tasks = {}
         self.old_create_task = create._create_task
         create._create_task = self.fake_create_task
 
     def tearDown(self):
         create._create_task = self.old_create_task
+        if self.old_task_id:
+            os.environ['TASK_ID'] = self.old_task_id
+        elif 'TASK_ID' in os.environ:
+            del os.environ['TASK_ID']
 
     def fake_create_task(self, session, task_id, label, task_def):
         self.created_tasks[task_id] = task_def
 
     def test_create_tasks(self):
         kind = FakeKind()
         tasks = {
             'tid-a': Task(kind=kind, label='a', task={'payload': 'hello world'}),
@@ -47,12 +55,28 @@ class TestCreate(unittest.TestCase):
         create.create_tasks(taskgraph, label_to_taskid)
 
         for tid, task in self.created_tasks.iteritems():
             self.assertEqual(task['payload'], 'hello world')
             # make sure the dependencies exist, at least
             for depid in task.get('dependencies', []):
                 self.assertIn(depid, self.created_tasks)
 
+    def test_create_task_without_dependencies(self):
+        "a task with no dependencies depends on the decision task"
+        os.environ['TASK_ID'] = 'decisiontask'
+        kind = FakeKind()
+        tasks = {
+            'tid-a': Task(kind=kind, label='a', task={'payload': 'hello world'}),
+        }
+        label_to_taskid = {'a': 'tid-a'}
+        graph = Graph(nodes={'tid-a'}, edges=set())
+        taskgraph = TaskGraph(tasks, graph)
+
+        create.create_tasks(taskgraph, label_to_taskid)
+
+        for tid, task in self.created_tasks.iteritems():
+            self.assertEqual(task['dependencies'], [os.environ['TASK_ID']])
+
 
 if __name__ == '__main__':
     main()