--- a/taskcluster/docs/parameters.rst
+++ b/taskcluster/docs/parameters.rst
@@ -99,16 +99,27 @@ syntax or reading a project-specific con
 
 ``target_tasks_method``
     The method to use to determine the target task set.  This is the suffix of
     one of the functions in ``taskcluster/taskgraph/target_tasks.py``.
 
 ``optimize_target_tasks``
     If true, then target tasks are eligible for optimization.
 
+``previous_graph_ids``
+    List of previous decision and action graph IDs to use as dependencies for this
+    graph. These are ordered; if the same task label is in multiple graphs, the
+    rightmost graph's task ID will be used.
+
+``previous_graph_kinds``
+    List of previous graph kinds to use as dependencies for this graph. Any tasks
+    in this graph with a kind in ``previous_graph_kinds`` will be replaced by the
+    corresponding task ID from the ``previous_graph_ids`` ``label-to-taskid.json``
+    if found.
+
 ``include_nightly``
     If true, then nightly tasks are eligible for optimization.
 
 Morphed Set
 -----------
 
 ``morph_templates``
     Dict of JSON-e templates to apply to each task, keyed by template name.

--- a/taskcluster/mach_commands.py
+++ b/taskcluster/mach_commands.py
@@ -123,16 +123,26 @@ class MachCommands(MachCommandBase):
                      help='Commit message to be parsed. Example: "try: -b do -p all -u all"')
     @CommandArgument('--project',
                      required=True,
                      help='Project to use for creating task graph. Example: --project=try')
     @CommandArgument('--pushlog-id',
                      dest='pushlog_id',
                      required=True,
                      default=0)
+    @CommandArgument('--previous-graph-ids',
+                     dest='previous_graph_ids',
+                     nargs='+',
+                     help='Decision taskIDs to use for previous task dependencies',
+                     default=[])
+    @CommandArgument('--previous-graph-kinds',
+                     dest='previous_graph_kinds',
+                     nargs='+',
+                     help='Kinds to use for previous task dependencies',
+                     default=[])
     @CommandArgument('--pushdate',
                      dest='pushdate',
                      required=True,
                      type=int,
                      default=0)
     @CommandArgument('--owner',
                      required=True,
                      help='email address of who owns this graph')

--- a/taskcluster/taskgraph/decision.py
+++ b/taskcluster/taskgraph/decision.py
@@ -147,16 +147,18 @@ def get_decision_parameters(options):
 
     """
     parameters = {n: options[n] for n in [
         'base_repository',
         'head_repository',
         'head_rev',
         'head_ref',
         'message',
+        'previous_graph_ids',
+        'previous_graph_kinds',
         'project',
         'pushlog_id',
         'pushdate',
         'owner',
         'level',
         'target_tasks_method',
     ] if n in options}
 

--- a/taskcluster/taskgraph/generator.py
+++ b/taskcluster/taskgraph/generator.py
@@ -10,16 +10,17 @@ import copy
 
 from . import filter_tasks
 from .graph import Graph
 from .taskgraph import TaskGraph
 from .task import Task
 from .optimize import optimize_task_graph
 from .morph import morph
 from .util.python_path import find_object
+from .util.taskcluster import get_artifact
 from .transforms.base import TransformSequence, TransformConfig
 from .util.verify import (
     verify_docs,
     verifications,
 )
 
 logger = logging.getLogger(__name__)
 
@@ -263,22 +264,33 @@ class TaskGraphGenerator(object):
                                  if t.attributes['kind'] == 'docker-image')
         target_graph = full_task_graph.graph.transitive_closure(target_tasks | docker_image_tasks)
         target_task_graph = TaskGraph(
             {l: all_tasks[l] for l in target_graph.nodes},
             target_graph)
         yield verifications('target_task_graph', target_task_graph)
 
         logger.info("Generating optimized task graph")
+        existing_tasks = None
+        if self.parameters.get('previous_graph_ids') and self.parameters.get('previous_graph_kinds'):
+            existing_tasks = {}
+            prev_graph_kinds = self.parameters['previous_graph_kinds']
+            for prev_graph_id in self.parameters['previous_graph_ids']:
+                kind_labels = set(t.label for t in full_task_graph.tasks.itervalues()
+                                  if t.attributes['kind'] in prev_graph_kinds)
+                prev_graph_tasks = get_artifact(prev_graph_id, 'public/label-to-taskid.json')
+                for label in set(prev_graph_tasks.keys()).intersection(kind_labels):
+                    existing_tasks[label] = prev_graph_tasks[label]
         do_not_optimize = set()
         if not self.parameters.get('optimize_target_tasks', True):
             do_not_optimize = target_task_set.graph.nodes
         optimized_task_graph, label_to_taskid = optimize_task_graph(target_task_graph,
                                                                     self.parameters,
-                                                                    do_not_optimize)
+                                                                    do_not_optimize,
+                                                                    existing_tasks=existing_tasks)
 
         yield verifications('optimized_task_graph', optimized_task_graph)
 
         morphed_task_graph, label_to_taskid = morph(
             optimized_task_graph, label_to_taskid, self.parameters)
 
         yield 'label_to_taskid', label_to_taskid
         yield verifications('morphed_task_graph', morphed_task_graph)

--- a/taskcluster/taskgraph/parameters.py
+++ b/taskcluster/taskgraph/parameters.py
@@ -20,16 +20,18 @@ PARAMETER_NAMES = set([
     'head_rev',
     'include_nightly',
     'level',
     'message',
     'morph_templates',
     'moz_build_date',
     'optimize_target_tasks',
     'owner',
+    'previous_graph_ids',
+    'previous_graph_kinds',
     'project',
     'pushdate',
     'pushlog_id',
     'target_task_labels',
     'target_tasks_method',
 ])
 
 TRY_ONLY_PARAMETERS = set([