diff --git a/core/modules/auto_updates/auto_updates.install b/core/modules/auto_updates/auto_updates.install
index a8d4486418..424c4e8e7b 100644
--- a/core/modules/auto_updates/auto_updates.install
+++ b/core/modules/auto_updates/auto_updates.install
@@ -68,3 +68,12 @@ function auto_updates_requirements($phase) {
   }
   return $requirements;
 }
+
+/**
+ * Implements hook_install().
+ */
+function auto_updates_install($is_syncing) {
+  /** @var \Drupal\auto_updates\ReadinessChecker\ReadinessCheckerManagerInterface $checker_manager */
+  $checker_manager = \Drupal::service('auto_updates.readiness_checker');
+  $checker_manager->run();
+}
diff --git a/core/modules/auto_updates/auto_updates.module b/core/modules/auto_updates/auto_updates.module
index 01199a5e07..71fd29dce1 100644
--- a/core/modules/auto_updates/auto_updates.module
+++ b/core/modules/auto_updates/auto_updates.module
@@ -62,17 +62,27 @@ function auto_updates_page_top(array &$page_top) {
  * Implements hook_cron().
  */
 function auto_updates_cron() {
-  $state = \Drupal::state();
   $request_time = \Drupal::time()->getRequestTime();
-  $last_check = $state->get('auto_updates.cron_last_check', 0);
+  /** @var \Drupal\auto_updates\ReadinessChecker\ReadinessCheckerManagerInterface $checker_manager */
+  $checker_manager = \Drupal::service('auto_updates.readiness_checker');
+  $last_check = $checker_manager->timestamp();
   // Only allow cron to run once every hour.
-  if (($request_time - $last_check) < 3600) {
+  if ($last_check && ($request_time - $last_check) < 3600) {
     return;
   }
 
   /** @var \Drupal\auto_updates\ReadinessChecker\ReadinessCheckerManagerInterface $checker */
   $checker = \Drupal::service('auto_updates.readiness_checker');
   $checker->run();
+}
 
-  $state->set('auto_updates.cron_last_check', \Drupal::time()->getCurrentTime());
+/**
+ * Implements hook_modules_installed().
+ */
+function auto_updates_modules_installed($modules) {
+  /** @var ReadinessCheckerManagerInterface $checker_manager */
+  $checker_manager = \Drupal::service('auto_updates.readiness_checker');
+  if ($checker_manager->clearResultsStaleResults()) {
+    $checker_manager->run();
+  }
 }
diff --git a/core/modules/auto_updates/src/ReadinessChecker/ReadinessCheckerManager.php b/core/modules/auto_updates/src/ReadinessChecker/ReadinessCheckerManager.php
index f218b63a27..e813912603 100644
--- a/core/modules/auto_updates/src/ReadinessChecker/ReadinessCheckerManager.php
+++ b/core/modules/auto_updates/src/ReadinessChecker/ReadinessCheckerManager.php
@@ -67,7 +67,6 @@ public function run() {
     }
     $messages_by_category = [];
     $sorted_checkers = $this->getSortedCheckers();
-
     foreach ($sorted_checkers as $category => $checkers) {
       foreach ($checkers as $checker) {
         if ($messages = $checker->run()) {
@@ -76,7 +75,12 @@ public function run() {
       }
     }
 
-    $this->keyValue->set("readiness_check_results.messages", $messages_by_category);
+    $this->keyValue->set("readiness_check_results",
+      [
+        'messages' => $messages_by_category,
+        'checkers' => $this->getCurrentCheckerIds(),
+      ]
+    );
     $this->keyValue->set('readiness_check_timestamp', \Drupal::time()->getRequestTime());
     return $messages_by_category;
   }
@@ -86,12 +90,25 @@ public function run() {
    */
   public function getResults($category) {
     if ($this->isEnabled()) {
-      $all_messages = $this->keyValue->get("readiness_check_results.messages", []);
+      $results = $this->keyValue->get("readiness_check_results", []);
+      $all_messages = $results['messages'] ?? [];
       return $all_messages[$category] ?? [];
     }
     return [];
   }
 
+  /**
+   * {@inheritdoc}
+   */
+  public function clearResultsStaleResults() {
+    $results = $this->keyValue->get('readiness_check_results');
+    if (isset($results['checkers']) && $this->getCurrentCheckerIds() !== $results['checkers']) {
+      $this->keyValue->delete('readiness_check_results');
+      return TRUE;
+    }
+    return FALSE;
+  }
+
   /**
    * {@inheritdoc}
    */
@@ -133,4 +150,20 @@ protected function getSortedCheckers() {
     return $sorted;
   }
 
+  /**
+   * Gets the current checker service Ids.
+   *
+   * @return string
+   *   A concatenated list of checker service Ids.
+   */
+  protected function getCurrentCheckerIds(): string {
+    $service_ids = [];
+    foreach ($this->getSortedCheckers() as $category => $checkers) {
+      foreach ($checkers as $checker) {
+        $service_ids[] = $checker->_serviceId;
+      }
+    }
+    return implode('::', $service_ids);
+  }
+
 }
diff --git a/core/modules/auto_updates/src/ReadinessChecker/ReadinessCheckerManagerInterface.php b/core/modules/auto_updates/src/ReadinessChecker/ReadinessCheckerManagerInterface.php
index a8d0d67605..b794df6af0 100644
--- a/core/modules/auto_updates/src/ReadinessChecker/ReadinessCheckerManagerInterface.php
+++ b/core/modules/auto_updates/src/ReadinessChecker/ReadinessCheckerManagerInterface.php
@@ -84,4 +84,12 @@ public function isEnabled();
    */
   public function getCategories();
 
+  /**
+   * Clears readiness checker results if the available checkers have changed.
+   *
+   * @return bool
+   *   Return TRUE if the results were cleared, otherwise returns FALSE.
+   */
+  public function clearResultsStaleResults();
+
 }
diff --git a/core/modules/auto_updates/tests/auto_updates_test/auto_updates_test.info.yml b/core/modules/auto_updates/tests/modules/auto_updates_test/auto_updates_test.info.yml
similarity index 100%
rename from core/modules/auto_updates/tests/auto_updates_test/auto_updates_test.info.yml
rename to core/modules/auto_updates/tests/modules/auto_updates_test/auto_updates_test.info.yml
diff --git a/core/modules/auto_updates/tests/auto_updates_test/auto_updates_test.services.yml b/core/modules/auto_updates/tests/modules/auto_updates_test/auto_updates_test.services.yml
similarity index 61%
rename from core/modules/auto_updates/tests/auto_updates_test/auto_updates_test.services.yml
rename to core/modules/auto_updates/tests/modules/auto_updates_test/auto_updates_test.services.yml
index 3508bd046c..12de8a27ba 100644
--- a/core/modules/auto_updates/tests/auto_updates_test/auto_updates_test.services.yml
+++ b/core/modules/auto_updates/tests/modules/auto_updates_test/auto_updates_test.services.yml
@@ -3,3 +3,6 @@ services:
     class: Drupal\auto_updates_test\ReadinessChecker\TestChecker
     tags:
       - { name: readiness_checker, category: error}
+  datetime.time:
+    class: Drupal\auto_updates_test\Datetime\TestTime
+    arguments: ['@request_stack']
diff --git a/core/modules/auto_updates/tests/modules/auto_updates_test/src/Datetime/TestTime.php b/core/modules/auto_updates/tests/modules/auto_updates_test/src/Datetime/TestTime.php
new file mode 100644
index 0000000000..3bbc9d606a
--- /dev/null
+++ b/core/modules/auto_updates/tests/modules/auto_updates_test/src/Datetime/TestTime.php
@@ -0,0 +1,26 @@
+<?php
+
+namespace Drupal\auto_updates_test\Datetime;
+
+use Drupal\Component\Datetime\Time;
+
+/**
+ * Test service for altering the request time.
+ */
+class TestTime extends Time {
+
+  const TIME_FORMAT = 'U';
+
+  const STATE_KEY = 'auto_updates_test.mock_date_time';
+
+  /**
+   * {@inheritdoc}
+   */
+  public function getRequestTime() {
+    if ($mock_date = \Drupal::state()->get(TestTime::STATE_KEY, NULL)) {
+      return \DateTime::createFromFormat(self::TIME_FORMAT, $mock_date)->getTimestamp();
+    }
+    return parent::getRequestTime();
+  }
+
+}
diff --git a/core/modules/auto_updates/tests/auto_updates_test/src/ReadinessChecker/TestChecker.php b/core/modules/auto_updates/tests/modules/auto_updates_test/src/ReadinessChecker/TestChecker.php
similarity index 73%
rename from core/modules/auto_updates/tests/auto_updates_test/src/ReadinessChecker/TestChecker.php
rename to core/modules/auto_updates/tests/modules/auto_updates_test/src/ReadinessChecker/TestChecker.php
index 8a27bfdc63..061984ce3f 100644
--- a/core/modules/auto_updates/tests/auto_updates_test/src/ReadinessChecker/TestChecker.php
+++ b/core/modules/auto_updates/tests/modules/auto_updates_test/src/ReadinessChecker/TestChecker.php
@@ -12,12 +12,14 @@ class TestChecker implements ReadinessCheckerInterface {
 
   use StringTranslationTrait;
 
+  const STATE_KEY = 'auto_updates_test.check_error';
+
   /**
    * {@inheritDoc}
    */
   public function run() {
-    if (\Drupal::state()->get('auto_update_test.check_error', FALSE)) {
-      return [$this->t('OMG 😱. Your site is not ready.')];
+    if ($message = \Drupal::state()->get(static::STATE_KEY, NULL)) {
+      return [$message];
     }
     return [];
   }
diff --git a/core/modules/auto_updates/tests/src/Functional/ReadinessCheckerTest.php b/core/modules/auto_updates/tests/src/Functional/ReadinessCheckerTest.php
index aaf865eb4f..79a01454d2 100644
--- a/core/modules/auto_updates/tests/src/Functional/ReadinessCheckerTest.php
+++ b/core/modules/auto_updates/tests/src/Functional/ReadinessCheckerTest.php
@@ -2,6 +2,8 @@
 
 namespace Drupal\Tests\auto_updates\Functional;
 
+use Drupal\auto_updates_test\Datetime\TestTime;
+use Drupal\auto_updates_test\ReadinessChecker\TestChecker;
 use Drupal\Tests\BrowserTestBase;
 
 /**
@@ -31,50 +33,60 @@ protected function setUp(): void {
    */
   public function testReadinessChecksStatusReport() {
     $assert = $this->assertSession();
-    $this->container->get('module_installer')->install(['auto_updates']);
+    $this->container->get('module_installer')->uninstall(['automated_cron']);
+    $this->container->get('module_installer')->install(['auto_updates', 'auto_updates_test']);
     $this->drupalGet('admin/reports/status');
     $assert->pageTextContains('Update readiness checks');
-    $assert->pageTextContains('Your site has never checked if it is ready to apply automatic updates.');
-    $assert->pageTextNotContains('Your site is ready to for automatic updates.');
+    $assert->pageTextContains('Your site is ready to for automatic updates.');
     $assert->pageTextNotContains('Run readiness checks manually');
     $this->drupalGet('admin/config/auto_updates/readiness');
     $assert->pageTextContains("Access denied");
 
+    // Confirm a user without the permission to run readiness checks does not
+    // have a link to run the checks when the checks need to run again.
+    $this->setFakeTime('+2 days');
+    $this->drupalGet('admin/reports/status');
+    $assert->pageTextNotContains('Your site is ready to for automatic updates.');
+    $assert->pageTextNotContains('Run readiness checks manually');
+    $assert->pageTextContains('Your site has not recently checked if it is ready to apply automatic updates');
+    $this->assertStringContainsString('Readiness checks were last run', $this->getReadinessReportText());
+
+    // Confirm a user with the permission to run readiness checks does have a
+    // link to run the checks when the checks need to run again.
     $this->drupalLogin($this->createUser([
       'administer site configuration',
       'administer software updates',
     ]));
-
     $this->drupalGet('admin/reports/status');
     $assert->pageTextContains('Update readiness checks');
-    $assert->pageTextContains('Your site has never checked if it is ready to apply automatic updates.');
+    $assert->pageTextContains('Your site has not recently checked if it is ready to apply automatic updates');
+    $this->assertStringContainsString('Last run', $this->getReadinessReportText());
     $assert->pageTextNotContains('Your site is ready to for automatic updates.');
-    $assert->pageTextContains('Run readiness checks manually');
+    $this->container->get('state')->set(TestChecker::STATE_KEY, 'OMG 😱. Your site is not ready.');
     $this->clickLink('Run readiness checks');
     $assert->pageTextNotContains("Access denied");
-    $assert->pageTextContains('No issues found. Your site is ready for automatic updates');
+    $assert->pageTextContains('Your site is currently failing readiness checks for automatic updates. It cannot be automatically updated until further action is performed:');
+    $assert->pageTextContains('OMG 😱. Your site is not ready.');
     // @todo If coming from the status report page should you be redirected there?
     //   This is how 'Run cron" works.
     $assert->addressEquals('/admin/config/auto_updates');
 
-    // Install a module that will fail a readiness check.
-    $this->container->get('state')->set('auto_update_test.check_error', TRUE);
-    $this->container->get('module_installer')->install(['auto_updates_test']);
-
+    // Confirm the error is displayed on the status report page.
     $this->drupalGet('admin/reports/status');
     $assert->pageTextContains('Update readiness checks');
     $assert->pageTextContains('OMG 😱. Your site is not ready.');
-    $assert->pageTextNotContains('Your site is ready to for automatic updates.');
+    $this->assertStringContainsString('1 check failed', $this->getReadinessReportText());
   }
 
   /**
    * Tests installing a module with a checker before installing auto_updates.
    */
-  public function testReadinessCheckBeforeInstall() {
+  public function testReadinessCheckAfterInstall() {
     $assert = $this->assertSession();
-
-    $this->container->get('state')->set('auto_update_test.check_error', TRUE);
-    $this->container->get('module_installer')->install(['auto_updates_test']);
+    $this->drupalLogin($this->createUser([
+      'administer site configuration',
+      'administer software updates',
+    ]));
 
     $this->drupalGet('admin/reports/status');
     $assert->pageTextNotContains('Update readiness checks');
@@ -82,8 +94,36 @@ public function testReadinessCheckBeforeInstall() {
     $this->container->get('module_installer')->install(['auto_updates']);
     $this->drupalGet('admin/reports/status');
     $assert->pageTextContains('Update readiness checks');
+    $assert->pageTextContains('Your site is ready to for automatic updates.');
+
+    $this->container->get('state')->set(TestChecker::STATE_KEY, 'OMG 😱. Your site is not ready.');
+    $this->container->get('module_installer')->install(['auto_updates_test']);
+    $this->drupalGet('admin/reports/status');
+    $assert->pageTextContains('Update readiness checks');
     $assert->pageTextContains('OMG 😱. Your site is not ready.');
     $assert->pageTextNotContains('Your site is ready to for automatic updates.');
+
+    // Confirm that installing a module that does not provider a new checker
+    // does not run the checkers on install.
+    $this->container->get('state')->set(TestChecker::STATE_KEY, 'OMG 🙀. Your site is not ready for a DIFFERENT reason');
+    $this->container->get('module_installer')->install(['color']);
+    $this->drupalGet('admin/reports/status');
+    $assert->pageTextContains('Update readiness checks');
+    $assert->pageTextNotContains('OMG 🙀. Your site is not read for a DIFFERENT reason');
+    $assert->pageTextContains('OMG 😱. Your site is not ready.');
+    $assert->pageTextNotContains('Your site is ready to for automatic updates.');
+
+    // Confirm the new message is displayed after running the checkers manually.
+    $this->drupalGet('admin/config/auto_updates');
+    $this->clickLink('run the readiness checks');
+    $assert->pageTextContains('OMG 🙀. Your site is not ready for a DIFFERENT reason');
+    $assert->pageTextNotContains('OMG 😱. Your site is not ready.');
+
+    $this->drupalGet('admin/reports/status');
+    $assert->pageTextContains('Update readiness checks');
+    $assert->pageTextContains('OMG 🙀. Your site is not ready for a DIFFERENT reason');
+    $assert->pageTextNotContains('OMG 😱. Your site is not ready.');
+    $assert->pageTextNotContains('Your site is ready to for automatic updates.');
   }
 
   /**
@@ -91,18 +131,53 @@ public function testReadinessCheckBeforeInstall() {
    */
   public function testCronRun() {
     $assert = $this->assertSession();
-    $this->container->get('module_installer')->install(['auto_updates']);
+    $this->container->get('module_installer')->install(['auto_updates', 'auto_updates_test']);
     $this->drupalGet('admin/reports/status');
     $assert->pageTextContains('Update readiness checks');
-    $assert->pageTextContains('Your site has never checked if it is ready to apply automatic updates.');
-    $assert->pageTextNotContains('Your site is ready to for automatic updates.');
-    $assert->pageTextNotContains('Run readiness checks manually');
+    $assert->pageTextContains('Your site is ready to for automatic updates.');
+
+    $this->container->get('state')->set(TestChecker::STATE_KEY, 'OMG 😱. Your site is not ready.');
 
+    // Tests that running cron within 1 hour of the checkers running will not
+    // run them again.
+    $this->setFakeTime('+30 minutes');
     $this->clickLink('Run cron');
     $assert->pageTextContains('Update readiness checks');
-    $assert->pageTextNotContains('Your site has never checked if it is ready to apply automatic updates.');
+    $assert->pageTextNotContains('OMG 😱. Your site is not ready.');
     $assert->pageTextContains('Your site is ready to for automatic updates.');
 
+    // Tests that running cron after 1 hour of the checkers running will run
+    // them again.
+    $this->setFakeTime('+65 minutes');
+    $this->clickLink('Run cron');
+    $assert->pageTextContains('Update readiness checks');
+    $assert->pageTextContains('OMG 😱. Your site is not ready.');
+    $assert->pageTextNotContains('Your site is ready to for automatic updates.');
+
+  }
+
+  /**
+   * Sets a fake time that will be used in that test.
+   *
+   * @param string $offset
+   *   A date/time offset string.
+   */
+  private function setFakeTime($offset): void {
+    $fake_delay = (new \DateTime())->modify($offset)->format(TestTime::TIME_FORMAT);
+    $this->container->get('state')->set(TestTime::STATE_KEY, $fake_delay);
+  }
+
+  /**
+   * Gets the text on status report page of the readiness report item.
+   *
+   * @return string
+   *   The readiness checks status report text.
+   */
+  private function getReadinessReportText() {
+    return $this->getSession()->getPage()->find(
+      'css',
+      'details.system-status-report__entry:contains("Update readiness checks")'
+    )->getText();
   }
 
 }