diff --git a/src/main/java/com/google/devtools/build/lib/shell/Command.java b/src/main/java/com/google/devtools/build/lib/shell/Command.java
index 8d9cffc..794be92 100644
--- a/src/main/java/com/google/devtools/build/lib/shell/Command.java
+++ b/src/main/java/com/google/devtools/build/lib/shell/Command.java
@@ -178,10 +178,20 @@
 
   /**
    * Creates a new {@link Command} for the given command line elements. The
-   * command line is executed exactly as given, without a shell. The given
-   * environment variables and working directory are used in subsequent
+   * command line is executed without a shell.
+   *
+   * The given environment variables and working directory are used in subsequent
    * calls to {@link #execute()}.
    *
+   * This command treats the  0-th element of {@code commandLineElement}
+   * (the name of an executable to run) specially.
+   * <ul>
+   *  <li>If it is an absolute path, it is used as it</li>
+   *  <li>If it is a single file name, the PATH lookup is performed</li>
+   *  <li>If it is a relative path that is not a single file name, the command will attempt to
+   *       execute the the binary at that path relative to {@code workingDirectory}.</li>
+   * </ul>
+   *
    * @param commandLineElements elements of raw command line to execute
    * @param environmentVariables environment variables to replace JVM's
    *  environment variables; may be null
@@ -189,12 +199,20 @@
    * working directory is used
    * @throws IllegalArgumentException if commandLine is null or empty
    */
-  public Command(final String[] commandLineElements,
-                 final Map<String, String> environmentVariables,
-                 final File workingDirectory) {
+  public Command(
+      String[] commandLineElements,
+      final Map<String, String> environmentVariables,
+      final File workingDirectory) {
     if (commandLineElements == null || commandLineElements.length == 0) {
       throw new IllegalArgumentException("command line is null or empty");
     }
+
+    File executable = new File(commandLineElements[0]);
+    if (!executable.isAbsolute() && executable.getParent() != null) {
+      commandLineElements = commandLineElements.clone();
+      commandLineElements[0] = new File(workingDirectory, commandLineElements[0]).getAbsolutePath();
+    }
+
     this.processBuilder =
       new ProcessBuilder(commandLineElements);
     if (environmentVariables != null) {
diff --git a/src/main/java/com/google/devtools/build/lib/worker/Worker.java b/src/main/java/com/google/devtools/build/lib/worker/Worker.java
index 8ad0a75..cb8d492 100644
--- a/src/main/java/com/google/devtools/build/lib/worker/Worker.java
+++ b/src/main/java/com/google/devtools/build/lib/worker/Worker.java
@@ -19,6 +19,7 @@
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.Path;
 
+import java.io.File;
 import java.io.IOException;
 import java.io.InputStream;
 import java.io.OutputStream;
@@ -58,8 +59,15 @@
     int workerId = pidCounter.getAndIncrement();
     Path logFile = logDir.getRelative("worker-" + workerId + "-" + key.getMnemonic() + ".log");
 
+    String[] command = key.getArgs().toArray(new String[0]);
+
+    // Follows the logic of {@link com.google.devtools.build.lib.shell.Command}.
+    File executable = new File(command[0]);
+    if (!executable.isAbsolute() && executable.getParent() != null) {
+      command[0] = new File(key.getWorkDir().getPathFile(), command[0]).getAbsolutePath();
+    }
     ProcessBuilder processBuilder =
-        new ProcessBuilder(key.getArgs().toArray(new String[0]))
+        new ProcessBuilder(command)
             .directory(key.getWorkDir().getPathFile())
             .redirectError(Redirect.appendTo(logFile.getPathFile()));
     processBuilder.environment().putAll(key.getEnv());
diff --git a/src/test/java/com/google/devtools/build/lib/shell/CommandTest.java b/src/test/java/com/google/devtools/build/lib/shell/CommandTest.java
index a5f81bd..771270f 100644
--- a/src/test/java/com/google/devtools/build/lib/shell/CommandTest.java
+++ b/src/test/java/com/google/devtools/build/lib/shell/CommandTest.java
@@ -20,6 +20,7 @@
 import static org.junit.Assert.assertTrue;
 import static org.junit.Assert.fail;
 
+import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.testutil.BlazeTestUtils;
 import com.google.devtools.build.lib.testutil.TestConstants;
 
@@ -682,4 +683,13 @@
     assertEquals(0, result.getStderr().length);
     assertEquals(expectedOutput, new String(result.getStdout()));
   }
+
+  @Test
+  public void testRelativePath() throws Exception {
+    Command command = new Command(new String[]{"relative/path/to/binary"},
+        ImmutableMap.<String, String>of(),
+        new File("/working/directory"));
+    assertThat(command.getCommandLineElements()[0])
+        .isEqualTo("/working/directory/relative/path/to/binary");
+  }
 }