--- a/tools/tryselect/mach_commands.py
+++ b/tools/tryselect/mach_commands.py
@@ -51,31 +51,81 @@ class TrySelect(MachCommandBase):
              description='Push selected tasks to the try server')
     @CommandArgument('args', nargs=argparse.REMAINDER)
     def try_default(self, args):
         """Push selected tests to the try server.
 
         The |mach try| command is a frontend for scheduling tasks to
         run on try server using selectors. A selector is a subcommand
         that provides its own set of command line arguments and are
-        listed below. Currently there is only single selector called
-        `syntax`, but more selectors will be added in the future.
+        listed below.
 
         If no subcommand is specified, the `syntax` selector is run by
         default. Run |mach try syntax --help| for more information on
         scheduling with the `syntax` selector.
         """
         parser = syntax_parser()
         kwargs = vars(parser.parse_args(args))
         return self._mach_context.commands.dispatch(
             'try', subcommand='syntax', context=self._mach_context, **kwargs)
 
     @SubCommand('try',
+                'fuzzy',
+                description='Select tasks on try using a fuzzy finder')
+    @CommandArgument('-u', '--update', action='store_true', default=False,
+                     help="Update fzf before running")
+    def try_fuzzy(self, update):
+        """Select which tasks to use with fzf.
+
+        This selector runs all task labels through a fuzzy finding interface.
+        All selected task labels and their dependencies will be scheduled on
+        try.
+
+        Keyboard Shortcuts
+        ------------------
+
+        When in the fuzzy finder interface, start typing to filter down the
+        task list. Then use the following keyboard shortcuts to select tasks:
+
+          accept: <enter>
+          cancel: <ctrl-c> or <esc>
+          cursor-up: <ctrl-k> or <up>
+          cursor-down: <ctrl-j> or <down>
+          toggle-select-down: <tab>
+          toggle-select-up: <shift-tab>
+          select-all: <ctrl-a>
+          deselect-all: <ctrl-d>
+          toggle-all: <ctrl-t>
+          clear-input: <alt-bspace>
+
+        There are many more shortcuts enabled by default, you can also define
+        your own shortcuts by setting `--bind` in the $FZF_DEFAULT_OPTS
+        environment variable. See `man fzf` for more info.
+
+        Extended Search
+        ---------------
+
+        When typing in search terms, the following modifiers can be applied:
+
+          'word: exact match (line must contain the literal string "word")
+          ^word: exact prefix match (line must start with literal "word")
+          word$: exact suffix match (line must end with literal "word")
+          !word: exact negation match (line must not contain literal "word")
+          'a | 'b: OR operator (joins two exact match operators together)
+
+        For example:
+
+          ^start 'exact | !ignore fuzzy end$
+        """
+        from tryselect.selectors.fuzzy import run_fuzzy_try
+        return run_fuzzy_try(update)
+
+    @SubCommand('try',
                 'syntax',
-                description='Push selected tasks using try syntax',
+                description='Select tasks on try using try syntax',
                 parser=syntax_parser)
     def try_syntax(self, **kwargs):
         """Push the current tree to try, with the specified syntax.
 
         Build options, platforms and regression tests may be selected
         using the usual try options (-b, -p and -u respectively). In
         addition, tests in a given directory may be automatically
         selected by passing that directory as a positional argument to the

new file mode 100644
--- /dev/null
+++ b/tools/tryselect/selectors/fuzzy.py
@@ -0,0 +1,198 @@
+# 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 os
+import platform
+import subprocess
+import sys
+from distutils.spawn import find_executable
+
+from mozboot.util import get_state_dir
+
+from ..tasks import generate_target
+from ..vcs import VCSHelper
+
+try:
+    import blessings
+    terminal = blessings.Terminal()
+except ImportError:
+    from mozlint.formatters.stylish import NullTerminal
+    terminal = NullTerminal()
+
+FZF_NOT_FOUND = """
+Could not find the `fzf` binary.
+
+The `mach try fuzzy` command depends on fzf. Please install it following the
+appropriate instructions for your platform:
+
+    https://github.com/junegunn/fzf#installation
+
+Only the binary is required, if you do not wish to install the shell and
+editor integrations, download the appropriate binary and put it on your $PATH:
+
+    https://github.com/junegunn/fzf-bin/releases
+""".lstrip()
+
+FZF_INSTALL_FAILED = """
+Failed to install fzf.
+
+Please install fzf manually following the appropriate instructions for your
+platform:
+
+    https://github.com/junegunn/fzf#installation
+
+Only the binary is required, if you do not wish to install the shell and
+editor integrations, download the appropriate binary and put it on your $PATH:
+
+    https://github.com/junegunn/fzf-bin/releases
+""".lstrip()
+
+FZF_RUN_INSTALL_WIZARD = """
+{t.bold}Running the fzf installation wizard.{t.normal}
+
+Only the fzf binary is required, if you do not wish to install the shell
+integrations, {t.bold}feel free to press 'n' at each of the prompts.{t.normal}
+""".format(t=terminal)
+
+FZF_HEADER = """
+For more shortcuts, see {t.italic_white}mach help try fuzzy{t.normal} and {t.italic_white}man fzf
+{shortcuts}
+""".strip()
+
+fzf_shortcuts = {
+    'ctrl-a': 'select-all',
+    'ctrl-d': 'deselect-all',
+    'ctrl-t': 'toggle-all',
+    'alt-bspace': 'beginning-of-line+kill-line',
+    '?': 'toggle-preview',
+}
+
+fzf_header_shortcuts = {
+    'cursor-up': 'ctrl-k',
+    'cursor-down': 'ctrl-j',
+    'toggle-select': 'tab',
+    'select-all': 'ctrl-a',
+    'accept': 'enter',
+    'cancel': 'ctrl-c',
+}
+
+
+def run(cmd, cwd=None):
+    is_win = platform.system() == 'Windows'
+    return subprocess.call(cmd, cwd=cwd, shell=True if is_win else False)
+
+
+def run_fzf_install_script(fzf_path, bin_only=False):
+    # We could run this without installing the shell integrations on all
+    # platforms, but those integrations are actually really useful so give user
+    # the choice.
+    if platform.system() == 'Windows':
+        cmd = ['bash', '-c', './install --bin']
+    else:
+        cmd = ['./install']
+        if bin_only:
+            cmd.append('--bin')
+        else:
+            print(FZF_RUN_INSTALL_WIZARD)
+
+    if run(cmd, cwd=fzf_path):
+        print(FZF_INSTALL_FAILED)
+        sys.exit(1)
+
+
+def fzf_bootstrap(update=False):
+    """Bootstrap fzf if necessary and return path to the executable.
+
+    The bootstrap works by cloning the fzf repository and running the included
+    `install` script. If update is True, we will pull the repository and re-run
+    the install script.
+    """
+    fzf_bin = find_executable('fzf')
+    if fzf_bin and not update:
+        return fzf_bin
+
+    fzf_path = os.path.join(get_state_dir()[0], 'fzf')
+    if update and not os.path.isdir(fzf_path):
+        print("fzf installed somewhere other than {}, please update manually".format(fzf_path))
+        sys.exit(1)
+
+    def get_fzf():
+        return find_executable('fzf', os.path.join(fzf_path, 'bin'))
+
+    if update:
+        ret = run(['git', 'pull'], cwd=fzf_path)
+        if ret:
+            print("Update fzf failed.")
+            sys.exit(1)
+
+        run_fzf_install_script(fzf_path, bin_only=True)
+        return get_fzf()
+
+    if os.path.isdir(fzf_path):
+        fzf_bin = get_fzf()
+        if fzf_bin:
+            return fzf_bin
+        # Fzf is cloned, but binary doesn't exist. Try running the install script
+        return fzf_bootstrap(update=True)
+
+    install = raw_input("Could not detect fzf, install it now? [y/n]: ")
+    if install.lower() != 'y':
+        return
+
+    if not find_executable('git'):
+        print("Git not found.")
+        print(FZF_INSTALL_FAILED)
+        sys.exit(1)
+
+    cmd = ['git', 'clone', '--depth', '1', 'https://github.com/junegunn/fzf.git']
+    if subprocess.call(cmd, cwd=os.path.dirname(fzf_path)):
+        print(FZF_INSTALL_FAILED)
+        sys.exit(1)
+
+    run_fzf_install_script(fzf_path)
+
+    print("Installed fzf to {}".format(fzf_path))
+    return get_fzf()
+
+
+def format_header():
+    shortcuts = []
+    for action, key in sorted(fzf_header_shortcuts.iteritems()):
+        shortcuts.append('{t.white}{action}{t.normal}: {t.yellow}<{key}>{t.normal}'.format(
+                         t=terminal, action=action, key=key))
+    return FZF_HEADER.format(shortcuts=', '.join(shortcuts), t=terminal)
+
+
+def run_fuzzy_try(update):
+    fzf = fzf_bootstrap(update)
+
+    if not fzf:
+        print(FZF_NOT_FOUND)
+        return
+
+    vcs = VCSHelper.create()
+    vcs.check_working_directory()
+
+    all_tasks = generate_target()
+
+    key_shortcuts = [k + ':' + v for k, v in fzf_shortcuts.iteritems()]
+    cmd = [
+        fzf, '-m',
+        '--bind', ','.join(key_shortcuts),
+        '--header', format_header(),
+        # Using python to split the preview string is a bit convoluted,
+        # but is guaranteed to be available on all platforms.
+        '--preview', 'python -c "print(\\"\\n\\".join(sorted([s.strip(\\"\'\\") for s in \\"{+}\\".split()])))"',  # noqa
+        '--preview-window=right:20%',
+    ]
+    proc = subprocess.Popen(cmd, stdout=subprocess.PIPE, stdin=subprocess.PIPE)
+    selected = proc.communicate('\n'.join(all_tasks))[0].splitlines()
+
+    if not selected:
+        print("no tasks selected")
+        return
+
+    return vcs.push_to_try("Pushed via 'mach try fuzzy', see diff for scheduled tasks", selected)

new file mode 100644
--- /dev/null
+++ b/tools/tryselect/tasks.py
@@ -0,0 +1,54 @@
+# 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 os
+
+from mozboot.util import get_state_dir
+from mozbuild.base import MozbuildObject
+from mozpack.files import FileFinder
+
+from taskgraph.generator import TaskGraphGenerator
+from taskgraph.parameters import load_parameters_file
+
+here = os.path.abspath(os.path.dirname(__file__))
+build = MozbuildObject.from_environment(cwd=here)
+
+
+def invalidate(cache):
+    if not os.path.isfile(cache):
+        return
+
+    tc_dir = os.path.join(build.topsrcdir, 'taskcluster')
+    tmod = max(os.path.getmtime(os.path.join(tc_dir, p)) for p, _ in FileFinder(tc_dir))
+    cmod = os.path.getmtime(cache)
+
+    if tmod > cmod:
+        os.remove(cache)
+
+
+def generate_target(params='project=mozilla-central'):
+    cache_dir = os.path.join(get_state_dir()[0], 'cache', 'taskgraph')
+    cache = os.path.join(cache_dir, 'target_task_set')
+
+    invalidate(cache)
+    if os.path.isfile(cache):
+        with open(cache, 'r') as fh:
+            return fh.read().splitlines()
+
+    if not os.path.isdir(cache_dir):
+        os.makedirs(cache_dir)
+
+    print("Task configuration changed, generating target tasks")
+    params = load_parameters_file(params)
+    params.check()
+
+    root = os.path.join(build.topsrcdir, 'taskcluster', 'ci')
+    tg = TaskGraphGenerator(root_dir=root, parameters=params).target_task_set
+    labels = [label for label in tg.graph.visit_postorder()]
+
+    with open(cache, 'w') as fh:
+        fh.write('\n'.join(labels))
+    return labels

--- a/tools/tryselect/vcs.py
+++ b/tools/tryselect/vcs.py
@@ -1,12 +1,14 @@
 # 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/.
 
+import json
+import os
 import subprocess
 import sys
 from abc import ABCMeta, abstractmethod, abstractproperty
 from distutils.spawn import find_executable
 
 GIT_CINNABAR_NOT_FOUND = """
 Could not detect `git-cinnabar`.
 
@@ -69,69 +71,86 @@ class VCSHelper(object):
     def run(self, cmd):
         try:
             return subprocess.check_output(cmd, stderr=subprocess.STDOUT)
         except subprocess.CalledProcessError as e:
             print("Error running `{}`:".format(' '.join(cmd)))
             print(e.output)
             raise
 
+    def write_task_config(self, labels):
+        config = os.path.join(self.root, 'try_task_config.json')
+        with open(config, 'w') as fh:
+            json.dump(sorted(labels), fh, indent=2)
+        return config
+
     def check_working_directory(self):
         if self.has_uncommitted_changes:
             print(UNCOMMITTED_CHANGES)
             sys.exit(1)
 
     @abstractmethod
-    def push_to_try(self, msg):
+    def push_to_try(self, msg, labels=None):
         pass
 
     @abstractproperty
     def files_changed(self):
         pass
 
     @abstractproperty
     def has_uncommitted_changes(self):
         pass
 
 
 class HgHelper(VCSHelper):
 
-    def push_to_try(self, msg):
+    def push_to_try(self, msg, labels=None):
         self.check_working_directory()
 
+        if labels:
+            config = self.write_task_config(labels)
+            self.run(['hg', 'add', config])
+
         try:
             return subprocess.check_call(['hg', 'push-to-try', '-m', msg])
         except subprocess.CalledProcessError:
             try:
                 self.run(['hg', 'showconfig', 'extensions.push-to-try'])
             except subprocess.CalledProcessError:
                 print(HG_PUSH_TO_TRY_NOT_FOUND)
             return 1
         finally:
             self.run(['hg', 'revert', '-a'])
 
+            if labels and os.path.isfile(config):
+                os.remove(config)
+
     @property
     def files_changed(self):
         return self.run(['hg', 'log', '-r', '::. and not public()',
                          '--template', '{join(files, "\n")}\n'])
 
     @property
     def has_uncommitted_changes(self):
         stat = [s for s in self.run(['hg', 'status', '-amrn']).split() if s]
         return len(stat) > 0
 
 
 class GitHelper(VCSHelper):
 
-    def push_to_try(self, msg):
+    def push_to_try(self, msg, labels=None):
         self.check_working_directory()
 
         if not find_executable('git-cinnabar'):
             print(GIT_CINNABAR_NOT_FOUND)
-            sys.exit(1)
+            return 1
+
+        if labels:
+            config = self.write_task_config(labels)
+            self.run(['git', 'add', config])
 
         subprocess.check_call(['git', 'commit', '--allow-empty', '-m', msg])
         try:
             return subprocess.call(['git', 'push', 'hg::ssh://hg.mozilla.org/try',
                                     '+HEAD:refs/heads/branches/default/tip'])
         finally:
             self.run(['git', 'reset', 'HEAD~'])