diff --git a/downloader.py b/downloader.py
index 7f53ec3..682a874 100755
--- a/downloader.py
+++ b/downloader.py
@@ -25,6 +25,8 @@
   """
 
   _LOG_TAG = 'DOWNLOAD'
+  # This filename must be kept in sync with clean_staged_images.py
+  _TIMESTAMP_FILENAME = 'staged.timestamp'
 
   def __init__(self, static_dir):
     self._static_dir = static_dir
@@ -61,11 +63,24 @@
     return '/'.join([rel_path, short_build])
 
   @staticmethod
+  def _TouchTimestampForStaged(directory_path):
+    file_name = os.path.join(directory_path, Downloader._TIMESTAMP_FILENAME)
+    # Easiest python version of |touch file_name|
+    with file(file_name, 'a'):
+      os.utime(file_name, None)
+
+  @staticmethod
   def BuildStaged(archive_url, static_dir):
     """Returns True if the build is already staged."""
     rel_path, short_build = Downloader.ParseUrl(archive_url)
     sub_directory = Downloader.GenerateLockTag(rel_path, short_build)
-    return os.path.isdir(os.path.join(static_dir, sub_directory))
+    directory_path = os.path.join(static_dir, sub_directory)
+    exists = os.path.isdir(directory_path)
+    # If the build exists, then touch the timestamp to tell
+    # clean_stages_images.py that we're using this build.
+    if exists:
+      Downloader._TouchTimestampForStaged(directory_path)
+    return exists
 
   def Download(self, archive_url, background=False):
     """Downloads the given build artifacts defined by the |archive_url|.
@@ -97,6 +112,7 @@
       # which would not be qualified as part of the suffix.
       self._staging_dir = tempfile.mkdtemp(suffix='_'.join(
           [rel_path.replace('/', '_'), short_build]))
+      Downloader._TouchTimestampForStaged(self._staging_dir)
       cherrypy.log('Gathering download requirements %s' % archive_url,
                    self._LOG_TAG)
       artifacts = self.GatherArtifactDownloads(
diff --git a/downloader_unittest.py b/downloader_unittest.py
index a7ce2b8..0a4e4ed 100755
--- a/downloader_unittest.py
+++ b/downloader_unittest.py
@@ -193,6 +193,9 @@
 
     self.assertTrue(downloader.Downloader.BuildStaged(archive_url,
                                                       self._work_dir))
+    self.assertTrue(os.path.exists(
+      os.path.join(os.path.join(self._work_dir, build_dir),
+        downloader.Downloader._TIMESTAMP_FILENAME)))
     self.assertFalse(downloader.Downloader.BuildStaged(archive_url_non_staged,
                                                        self._work_dir))
   def testTrybotBuildStaged(self):