diff --git a/lib/paygen/paygen_build_lib.py b/lib/paygen/paygen_build_lib.py
index 290ef7a..b9d383e 100644
--- a/lib/paygen/paygen_build_lib.py
+++ b/lib/paygen/paygen_build_lib.py
@@ -306,6 +306,25 @@
     return [p for p in self.payloads
             if set(p['labels']).issuperset(labels)]
 
+  def GetOnly(self, labels):
+    """Retrieve all payloads with label sets that are equal to |labels|.
+
+    Args:
+      labels: A list of strings.
+
+    Returns:
+      A list of gspath.Payload objects with label sets equal to |labels|.
+
+    Raises:
+      ValueError if |labels| is not a list.
+    """
+    if not isinstance(labels, list):
+      raise ValueError('PayloadManager.GetOnly expects a list of labels.'
+                       ' Given %s' % type(labels))
+
+    labels = set(labels)
+    return [p for p in self.payloads if set(p['labels']) == labels]
+
 
 class _PaygenBuild(object):
   """This class is responsible for generating the payloads for a given build.
@@ -395,7 +414,6 @@
     self._skip_nontest_payloads = skip_nontest_payloads
     self._control_dir = control_dir
     self._output_dir = output_dir
-    self._previous_version = None
     self._run_parallel = run_parallel
     self._run_on_builder = run_on_builder
     self._archive_board = None
@@ -872,13 +890,19 @@
 
     _LogList('Images found', images)
 
-    # Discover active FSI builds. We need these for generating deltas.
+    # Discover and filter active FSI builds.
     fsi_builds = self._DiscoverFsiBuildsForDeltas()
     if fsi_builds:
       _LogList('Active FSI builds considered', fsi_builds)
     else:
       logging.info('No active FSI builds found')
 
+    for fsi in fsi_builds:
+      fsi_images += self._DiscoverImages(fsi)
+      fsi_images += self._DiscoverTestImageArchives(fsi)
+
+    fsi_images = _FilterForBasic(fsi_images) + _FilterForTest(fsi_images)
+
     # Discover previous, non-FSI, builds that we also must generate deltas for.
     previous_builds = [b for b in self._DiscoverNmoBuild()
                        if b not in fsi_builds]
@@ -887,13 +911,6 @@
     else:
       logging.info('No other previous builds found')
 
-    # Discover and filter FSI images.
-    for fsi in fsi_builds:
-      fsi_images += self._DiscoverImages(fsi)
-      fsi_images += self._DiscoverTestImageArchives(fsi)
-
-    fsi_images = _FilterForBasic(fsi_images) + _FilterForTest(fsi_images)
-
     # Discover and filter previous images.
     for p in previous_builds:
       try:
@@ -904,14 +921,6 @@
         # TODO(mtennant): Remove this when bug is fixed properly.
         logging.warning('Previous build image is missing, skipping: %s', e)
 
-        # We also clear the previous version field so that subsequent code does
-        # not attempt to generate a full update test from the N-1 version;
-        # since this version has missing images, no payloads were generated for
-        # it and test generation is bound to fail.
-        # TODO(garnold) This should be reversed together with the rest of this
-        # block.
-        self._previous_version = None
-
         # In this case, we should also skip test image discovery; since no
         # signed deltas will be generated from this build, we don't need to
         # generate test deltas from it.
@@ -921,13 +930,21 @@
     previous_images = (
         _FilterForBasic(previous_images) + _FilterForTest(previous_images))
 
-    # Discover full payloads for all non-test images in the current build.
+    # Discover and catalogue full, non-test payloads.
     skip_full = self._skip_full_payloads or self._skip_nontest_payloads
+
+    # Full payloads for the current build.
     payload_manager.Add(
         ['full'],
         self._DiscoverRequiredFullPayloads(_FilterForImages(images)),
         skip=skip_full)
 
+    # Full payloads for previous builds.
+    payload_manager.Add(
+        ['full', 'previous'],
+        self._DiscoverRequiredFullPayloads(_FilterForImages(previous_images)),
+        skip=skip_full)
+
     # Discover delta payloads.
     skip_deltas = self._skip_delta_payloads or self._skip_nontest_payloads
 
@@ -983,6 +1000,12 @@
           self._DiscoverRequiredFullPayloads(_FilterForTest(images)),
           skip=skip_test_full)
 
+      # Full previous payloads.
+      payload_manager.Add(
+          ['test', 'full', 'previous'],
+          self._DiscoverRequiredFullPayloads(_FilterForTest(previous_images)),
+          skip=skip_test_full)
+
       # Deltas for current -> NPO (test payloads).
       payload_manager.Add(
           ['test', 'delta', 'npo'],
@@ -1311,59 +1334,55 @@
     """
     payload_tests = []
 
-    for p in payload_manager.Get([]):
-      # We are only testing test payloads.
-      if not 'test' in p.labels:
-        continue
+    # Pre-fetch lab stable FSIs.
+    lab_stable_fsi_deltas = self._DiscoverAllFsiBuildsForDeltaTesting()
+    lab_stable_fsi_full = self._DiscoverAllFsiBuildsForFullTesting()
 
-      # Distinguish between delta and full payloads.
-      if not 'delta' in p.labels:
-        # Create a full update test from NMO, if we are newer.
-        if not self._previous_version:
-          logging.warning('No previous build, not testing full update %s from '
-                          'NMO', p)
-        elif gspaths.VersionGreater(
-            self._previous_version, p.tgt_image.version):
+    def IsFsiLabStable(fsi_image):
+      for build in lab_stable_fsi_deltas:
+        if all([fsi_image.board == build.board,
+                fsi_image.channel == build.channel,
+                fsi_image.version == build.version,
+                fsi_image.bucket == build.bucket]):
+          return True
+      return False
+
+    # Create full update tests that involve the current build.
+    for p in payload_manager.GetOnly(['test', 'full']):
+
+      # Update tests from previous to current, if we are newer.
+      for p_prev in payload_manager.GetOnly(['test', 'full', 'previous']):
+        if gspaths.VersionGreater(p_prev.tgt_image.version,
+                                  p.tgt_image.version):
           logging.warning(
               'NMO (%s) is newer than target (%s), skipping NMO full '
-              'update test.', self._previous_version, p)
-        else:
-          payload_tests.append(self.PayloadTest(
-              p, src_channel=self._build.channel,
-              src_version=self._previous_version))
+              'update test.', p_prev, p)
+          continue
 
-        # Create a full update test from the current version to itself.
         payload_tests.append(self.PayloadTest(
             p,
-            src_channel=self._build.channel,
-            src_version=self._build.version))
+            src_channel=p_prev.tgt_image.channel,
+            src_version=p_prev.tgt_image.version))
 
-        # Create a full update test from oldest viable FSI.
-        payload_tests += self._CreateFsiPayloadTests(
-            p, self._DiscoverAllFsiBuildsForFullTesting())
-      else:
-        # Create a delta update test.
+      # Update test from current version to itself.
+      payload_tests.append(self.PayloadTest(
+          p,
+          src_channel=self._build.channel,
+          src_version=self._build.version))
 
-        # FSI deltas are included only if they are lab stable.
-        if 'fsi' in p.labels:
-          fsi_image = p.src_image
-          is_lab_stable = False
+      # Update test from the oldest viable FSI.
+      payload_tests += self._CreateFsiPayloadTests(p, lab_stable_fsi_full)
 
-          for build in self._DiscoverAllFsiBuildsForDeltaTesting():
-            if all([fsi_image.board == build.board,
-                    fsi_image.channel == build.channel,
-                    fsi_image.version == build.version,
-                    fsi_image.bucket == build.bucket]):
-              is_lab_stable = True
-              break
+    # Create delta payload tests.
+    for p in payload_manager.Get(['test', 'delta']):
+      # FSI deltas are included only if they are known to be lab stable.
+      if 'fsi' in p.labels and not IsFsiLabStable(p.src_image):
+        logging.warning(
+            'FSI delta payload (%s) is not lab stable, skipping '
+            'delta update test', p)
+        continue
 
-          if not is_lab_stable:
-            logging.warning(
-                'FSI delta payload (%s) is not lab stable, skipping '
-                'delta update test', p)
-            continue
-
-        payload_tests.append(self.PayloadTest(p))
+      payload_tests.append(self.PayloadTest(p))
 
     return payload_tests
 
diff --git a/lib/paygen/paygen_build_lib_unittest.py b/lib/paygen/paygen_build_lib_unittest.py
index 85c8e16..f828e14 100644
--- a/lib/paygen/paygen_build_lib_unittest.py
+++ b/lib/paygen/paygen_build_lib_unittest.py
@@ -74,6 +74,18 @@
     self.assertEquals([p1, p2], pm.Get(['test']))
     self.assertEquals([], pm.Get(['foo', 'bar']))
 
+  def testGetOnly(self):
+    """Test retrieving payloads from the manager."""
+    pm = paygen_build_lib.PayloadManager()
+
+    p1 = gspaths.Payload(tgt_image='bar', labels=['bar', 'test'])
+    p2 = gspaths.Payload(tgt_image='bar', labels=['bar', 'test', 'test2'])
+
+    pm.payloads = [p1, p2]
+
+    self.assertEquals([p1, p2], pm.Get(['bar', 'test']))
+    self.assertEquals([p1], pm.GetOnly(['bar', 'test']))
+
 
 class BasePaygenBuildLibTest(cros_test_lib.MoxTempDirTestCase):
   """Base class for testing PaygenBuildLib class."""
@@ -690,6 +702,8 @@
     # Run the test verification.
     self.mox.ReplayAll()
 
+    self.maxDiff = None
+
     payload_manager = paygen._DiscoverRequiredPayloads()
 
     expected = [gspaths.Payload(tgt_image=self.basic_image, uri=output_uri,
@@ -700,6 +714,11 @@
                                 labels=['full']),
                 gspaths.Payload(tgt_image=self.premp_npo_image, uri=output_uri,
                                 labels=['full']),
+
+                gspaths.Payload(tgt_image=nmo_images[0], uri=output_uri,
+                                labels=['full', 'previous']),
+                gspaths.Payload(tgt_image=nmo_images[1], uri=output_uri,
+                                labels=['full', 'previous']),
                 # NPO Deltas
                 gspaths.Payload(tgt_image=self.npo_image,
                                 src_image=self.basic_image,
@@ -740,6 +759,9 @@
                 gspaths.Payload(tgt_image=self.test_image,
                                 uri=output_uri,
                                 labels=['test', 'full']),
+                gspaths.Payload(tgt_image=nmo_test_image,
+                                uri=output_uri,
+                                labels=['test', 'full', 'previous']),
 
                 # Test NPO delta.
                 gspaths.Payload(tgt_image=self.test_image,
@@ -1353,6 +1375,7 @@
   def setupCreatePayloadTests(self):
     paygen = self._GetPaygenBuildInstance()
 
+    self.mox.StubOutWithMock(paygen, '_DiscoverAllFsiBuildsForDeltaTesting')
     self.mox.StubOutWithMock(paygen, '_DiscoverAllFsiBuildsForFullTesting')
     self.mox.StubOutWithMock(paygen, '_FindFullTestPayloads')
 
@@ -1366,6 +1389,9 @@
 
     paygen = self.setupCreatePayloadTests()
 
+    paygen._DiscoverAllFsiBuildsForDeltaTesting().AndReturn([])
+    paygen._DiscoverAllFsiBuildsForFullTesting().AndReturn([])
+
     # Run the test verification.
     self.mox.ReplayAll()
 
@@ -1380,12 +1406,13 @@
     ]
 
     payload_manager = paygen_build_lib.PayloadManager()
-    payload_manager.Add(['test'], [payloads[0]])
+    payload_manager.Add(['test', 'full'], [payloads[0]])
     payload_manager.Add(['test', 'delta'], [payloads[1]])
 
     paygen = self.setupCreatePayloadTests()
 
     # We search for FSIs once for each full payload.
+    paygen._DiscoverAllFsiBuildsForDeltaTesting().AndReturn(['0.9.9', '1.0.0'])
     paygen._DiscoverAllFsiBuildsForFullTesting().AndReturn(['0.9.9', '1.0.0'])
     paygen._FindFullTestPayloads('stable-channel', '0.9.9').AndReturn(False)
     paygen._FindFullTestPayloads('stable-channel', '1.0.0').AndReturn(True)
@@ -1396,7 +1423,7 @@
     self.maxDiff = None
 
     labelled_payloads = [
-        gspaths.Payload(tgt_image=self.test_image, labels=['test']),
+        gspaths.Payload(tgt_image=self.test_image, labels=['test', 'full']),
         gspaths.Payload(tgt_image=self.prev_image, src_image=self.test_image,
                         labels=['test', 'delta'])
     ]
@@ -1422,9 +1449,8 @@
 
     paygen = self.setupCreatePayloadTests()
 
-    self.mox.StubOutWithMock(paygen, '_DiscoverAllFsiBuildsForDeltaTesting')
-
     paygen._DiscoverAllFsiBuildsForDeltaTesting().AndReturn([self.foo_build])
+    paygen._DiscoverAllFsiBuildsForFullTesting().AndReturn([])
 
     self.mox.ReplayAll()
 
@@ -1445,12 +1471,11 @@
 
     paygen = self.setupCreatePayloadTests()
 
-    self.mox.StubOutWithMock(paygen, '_DiscoverAllFsiBuildsForDeltaTesting')
-
     paygen._DiscoverAllFsiBuildsForDeltaTesting().AndReturn(
         [gspaths.Build(bucket='crt', channel='not-foo-channel',
                        board='foo-board', version='1.2.3')]
     )
+    paygen._DiscoverAllFsiBuildsForFullTesting().AndReturn([])
 
     self.mox.ReplayAll()
 
@@ -1955,7 +1980,6 @@
                                version='1.1.0')
 
     nmo_images = self._GetBuildImages(nmo_build)
-    nmo_test_image = self._GetBuildTestImage(nmo_build)
     fsi1_images = self._GetBuildImages(fsi1_build)
     fsi1_test_image = self._GetBuildTestImage(fsi1_build)
     fsi2_images = self._GetBuildImages(fsi2_build)
@@ -1964,13 +1988,13 @@
     paygen._DiscoverImages(paygen._build).AndReturn(self.images)
     paygen._DiscoverTestImageArchives(paygen._build).AndReturn([])
     paygen._DiscoverFsiBuildsForDeltas().AndReturn([fsi1_build, fsi2_build])
-    paygen._DiscoverNmoBuild().AndReturn([nmo_build])
     paygen._DiscoverImages(fsi1_build).AndReturn(fsi1_images)
     paygen._DiscoverTestImageArchives(fsi1_build).AndReturn([fsi1_test_image])
     paygen._DiscoverImages(fsi2_build).AndReturn(fsi2_images)
     paygen._DiscoverTestImageArchives(fsi2_build).AndReturn([fsi2_test_image])
+    paygen._DiscoverNmoBuild().AndReturn([nmo_build])
     paygen._DiscoverImages(nmo_build).AndReturn(nmo_images)
-    paygen._DiscoverTestImageArchives(nmo_build).AndReturn([nmo_test_image])
+    paygen._DiscoverTestImageArchives(nmo_build).AndReturn([])
 
     # Simplify the output URIs, so it's easy to check them below.
     paygen_payload_lib.DefaultPayloadUri(
@@ -1979,6 +2003,8 @@
     # Run the test verification.
     self.mox.ReplayAll()
 
+    self.maxDiff = None
+
     payload_manager = paygen._DiscoverRequiredPayloads()
 
     expected = [
@@ -1990,6 +2016,11 @@
                         labels=['full']),
         gspaths.Payload(tgt_image=self.premp_npo_image, uri=output_uri,
                         labels=['full']),
+
+        gspaths.Payload(tgt_image=nmo_images[0], uri=output_uri,
+                        labels=['full', 'previous']),
+        gspaths.Payload(tgt_image=nmo_images[1], uri=output_uri,
+                        labels=['full', 'previous']),
         # No NPO Deltas because the basic images have different image types.
 
         # NMO deltas.