diff --git a/tools/releasetools/add_img_to_target_files.py b/tools/releasetools/add_img_to_target_files.py
index 3884f49..6852d02 100755
--- a/tools/releasetools/add_img_to_target_files.py
+++ b/tools/releasetools/add_img_to_target_files.py
@@ -383,6 +383,14 @@
       if recovery_image:
         recovery_image.AddToZip(output_zip)
 
+      banner("recovery (two-step image)")
+      # The special recovery.img for two-step package use.
+      recovery_two_step_image = common.GetBootableImage(
+          "IMAGES/recovery-two-step.img", "recovery-two-step.img",
+          OPTIONS.input_tmp, "RECOVERY", two_step_image=True)
+      if recovery_two_step_image:
+        recovery_two_step_image.AddToZip(output_zip)
+
   banner("system")
   system_img_path = AddSystem(
     output_zip, recovery_img=recovery_image, boot_img=boot_image)
diff --git a/tools/releasetools/common.py b/tools/releasetools/common.py
index 79b218f..8ed12dc 100644
--- a/tools/releasetools/common.py
+++ b/tools/releasetools/common.py
@@ -395,13 +395,17 @@
 
 
 def _BuildBootableImage(sourcedir, fs_config_file, info_dict=None,
-                        has_ramdisk=False):
+                        has_ramdisk=False, two_step_image=False):
   """Build a bootable image from the specified sourcedir.
 
   Take a kernel, cmdline, and optionally a ramdisk directory from the input (in
-  'sourcedir'), and turn them into a boot image.  Return the image data, or
-  None if sourcedir does not appear to contains files for building the
-  requested image."""
+  'sourcedir'), and turn them into a boot image. 'two_step_image' indicates if
+  we are building a two-step special image (i.e. building a recovery image to
+  be loaded into /boot in two-step OTAs).
+
+  Return the image data, or None if sourcedir does not appear to contains files
+  for building the requested image.
+  """
 
   def make_ramdisk():
     ramdisk_img = tempfile.NamedTemporaryFile()
@@ -485,7 +489,12 @@
 
   if (info_dict.get("boot_signer", None) == "true" and
       info_dict.get("verity_key", None)):
-    path = "/" + os.path.basename(sourcedir).lower()
+    # Hard-code the path as "/boot" for two-step special recovery image (which
+    # will be loaded into /boot during the two-step OTA).
+    if two_step_image:
+      path = "/boot"
+    else:
+      path = "/" + os.path.basename(sourcedir).lower()
     cmd = [OPTIONS.boot_signer_path]
     cmd.extend(OPTIONS.boot_signer_args)
     cmd.extend([path, img.name,
@@ -539,7 +548,7 @@
 
 
 def GetBootableImage(name, prebuilt_name, unpack_dir, tree_subdir,
-                     info_dict=None):
+                     info_dict=None, two_step_image=False):
   """Return a File object with the desired bootable image.
 
   Look for it in 'unpack_dir'/BOOTABLE_IMAGES under the name 'prebuilt_name',
@@ -571,7 +580,7 @@
   fs_config = "META/" + tree_subdir.lower() + "_filesystem_config.txt"
   data = _BuildBootableImage(os.path.join(unpack_dir, tree_subdir),
                              os.path.join(unpack_dir, fs_config),
-                             info_dict, has_ramdisk)
+                             info_dict, has_ramdisk, two_step_image)
   if data:
     return File(name, data)
   return None
diff --git a/tools/releasetools/img_from_target_files.py b/tools/releasetools/img_from_target_files.py
index aa21d7e..84e0e63 100755
--- a/tools/releasetools/img_from_target_files.py
+++ b/tools/releasetools/img_from_target_files.py
@@ -86,6 +86,8 @@
             continue
           if not image.endswith(".img"):
             continue
+          if image == "recovery-two-step.img":
+            continue
           common.ZipWrite(
               output_zip, os.path.join(images_path, image), image)
         done = True
diff --git a/tools/releasetools/ota_from_target_files.py b/tools/releasetools/ota_from_target_files.py
index 403a3a4..b11e85d 100755
--- a/tools/releasetools/ota_from_target_files.py
+++ b/tools/releasetools/ota_from_target_files.py
@@ -461,6 +461,39 @@
       script.AssertOemProperty(prop, oem_dict.get(prop))
 
 
+def _WriteRecoveryImageToBoot(script, output_zip):
+  """Find and write recovery image to /boot in two-step OTA.
+
+  In two-step OTAs, we write recovery image to /boot as the first step so that
+  we can reboot to there and install a new recovery image to /recovery.
+  A special "recovery-two-step.img" will be preferred, which encodes the correct
+  path of "/boot". Otherwise the device may show "device is corrupt" message
+  when booting into /boot.
+
+  Fall back to using the regular recovery.img if the two-step recovery image
+  doesn't exist. Note that rebuilding the special image at this point may be
+  infeasible, because we don't have the desired boot signer and keys when
+  calling ota_from_target_files.py.
+  """
+
+  recovery_two_step_img_name = "recovery-two-step.img"
+  recovery_two_step_img_path = os.path.join(
+      OPTIONS.input_tmp, "IMAGES", recovery_two_step_img_name)
+  if os.path.exists(recovery_two_step_img_path):
+    recovery_two_step_img = common.GetBootableImage(
+        recovery_two_step_img_name, recovery_two_step_img_name,
+        OPTIONS.input_tmp, "RECOVERY")
+    common.ZipWriteStr(
+        output_zip, recovery_two_step_img_name, recovery_two_step_img.data)
+    print "two-step package: using %s in stage 1/3" % (
+        recovery_two_step_img_name,)
+    script.WriteRawImage("/boot", recovery_two_step_img_name)
+  else:
+    print "two-step package: using recovery.img in stage 1/3"
+    # The "recovery.img" entry has been written into package earlier.
+    script.WriteRawImage("/boot", "recovery.img")
+
+
 def HasRecoveryPatch(target_files_zip):
   namelist = [name for name in target_files_zip.namelist()]
   return ("SYSTEM/recovery-from-boot.p" in namelist or
@@ -609,6 +642,9 @@
     script.AppendExtra("""
 if get_stage("%(bcb_dev)s") == "2/3" then
 """ % bcb_dev)
+
+    # Stage 2/3: Write recovery image to /recovery (currently running /boot).
+    script.Comment("Stage 2/3")
     script.WriteRawImage("/recovery", "recovery.img")
     script.AppendExtra("""
 set_stage("%(bcb_dev)s", "3/3");
@@ -616,6 +652,9 @@
 else if get_stage("%(bcb_dev)s") == "3/3" then
 """ % bcb_dev)
 
+    # Stage 3/3: Make changes.
+    script.Comment("Stage 3/3")
+
   # Dump fingerprints
   script.Print("Target: %s" % target_fp)
 
@@ -714,7 +753,11 @@
 set_stage("%(bcb_dev)s", "");
 """ % bcb_dev)
     script.AppendExtra("else\n")
-    script.WriteRawImage("/boot", "recovery.img")
+
+    # Stage 1/3: Nothing to verify for full OTA. Write recovery image to /boot.
+    script.Comment("Stage 1/3")
+    _WriteRecoveryImageToBoot(script, output_zip)
+
     script.AppendExtra("""
 set_stage("%(bcb_dev)s", "2/3");
 reboot_now("%(bcb_dev)s", "");
@@ -938,6 +981,9 @@
     script.AppendExtra("""
 if get_stage("%(bcb_dev)s") == "2/3" then
 """ % bcb_dev)
+
+    # Stage 2/3: Write recovery image to /recovery (currently running /boot).
+    script.Comment("Stage 2/3")
     script.AppendExtra("sleep(20);\n")
     script.WriteRawImage("/recovery", "recovery.img")
     script.AppendExtra("""
@@ -946,6 +992,9 @@
 else if get_stage("%(bcb_dev)s") != "3/3" then
 """ % bcb_dev)
 
+    # Stage 1/3: (a) Verify the current system.
+    script.Comment("Stage 1/3")
+
   # Dump fingerprints
   script.Print(source_fp)
   script.Print(target_fp)
@@ -1016,13 +1065,18 @@
   device_specific.IncrementalOTA_VerifyEnd()
 
   if OPTIONS.two_step:
-    script.WriteRawImage("/boot", "recovery.img")
+    # Stage 1/3: (b) Write recovery image to /boot.
+    _WriteRecoveryImageToBoot(script, output_zip)
+
     script.AppendExtra("""
 set_stage("%(bcb_dev)s", "2/3");
 reboot_now("%(bcb_dev)s", "");
 else
 """ % bcb_dev)
 
+    # Stage 3/3: Make changes.
+    script.Comment("Stage 3/3")
+
   # Verify the existing partitions.
   system_diff.WriteVerifyScript(script, touched_blocks_only=True)
   if vendor_diff:
@@ -1615,6 +1669,9 @@
     script.AppendExtra("""
 if get_stage("%(bcb_dev)s") == "2/3" then
 """ % bcb_dev)
+
+    # Stage 2/3: Write recovery image to /recovery (currently running /boot).
+    script.Comment("Stage 2/3")
     script.AppendExtra("sleep(20);\n")
     script.WriteRawImage("/recovery", "recovery.img")
     script.AppendExtra("""
@@ -1623,6 +1680,9 @@
 else if get_stage("%(bcb_dev)s") != "3/3" then
 """ % bcb_dev)
 
+    # Stage 1/3: (a) Verify the current system.
+    script.Comment("Stage 1/3")
+
   # Dump fingerprints
   script.Print("Source: %s" % (source_fp,))
   script.Print("Target: %s" % (target_fp,))
@@ -1667,13 +1727,18 @@
   device_specific.IncrementalOTA_VerifyEnd()
 
   if OPTIONS.two_step:
-    script.WriteRawImage("/boot", "recovery.img")
+    # Stage 1/3: (b) Write recovery image to /boot.
+    _WriteRecoveryImageToBoot(script, output_zip)
+
     script.AppendExtra("""
 set_stage("%(bcb_dev)s", "2/3");
 reboot_now("%(bcb_dev)s", "");
 else
 """ % bcb_dev)
 
+    # Stage 3/3: Make changes.
+    script.Comment("Stage 3/3")
+
   script.Comment("---- start making changes here ----")
 
   device_specific.IncrementalOTA_InstallBegin()