diff --git a/core/modules/content_moderation/src/Plugin/WorkflowType/ContentModeration.php b/core/modules/content_moderation/src/Plugin/WorkflowType/ContentModeration.php
index 358314a..fd4052d 100644
--- a/core/modules/content_moderation/src/Plugin/WorkflowType/ContentModeration.php
+++ b/core/modules/content_moderation/src/Plugin/WorkflowType/ContentModeration.php
@@ -3,6 +3,7 @@
 namespace Drupal\content_moderation\Plugin\WorkflowType;
 
 use Drupal\content_moderation\ModerationInformationInterface;
+use Drupal\Core\Cache\RefinableCacheableDependencyInterface;
 use Drupal\Core\Entity\ContentEntityInterface;
 use Drupal\Core\Entity\EntityTypeBundleInfoInterface;
 use Drupal\Core\Entity\EntityTypeManagerInterface;
@@ -108,7 +109,8 @@ public function getState($state_id) {
   /**
    * {@inheritdoc}
    */
-  public function workflowHasData(WorkflowInterface $workflow) {
+  public function workflowHasData(WorkflowInterface $workflow, RefinableCacheableDependencyInterface $cacheability_metadata) {
+    $cacheability_metadata->addCacheTags(['content_moderation_state_list']);
     return (bool) $this->entityTypeManager
       ->getStorage('content_moderation_state')
       ->getQuery()
@@ -122,7 +124,8 @@ public function workflowHasData(WorkflowInterface $workflow) {
   /**
    * {@inheritdoc}
    */
-  public function workflowStateHasData(WorkflowInterface $workflow, StateInterface $state) {
+  public function workflowStateHasData(WorkflowInterface $workflow, StateInterface $state, RefinableCacheableDependencyInterface $cacheability_metadata) {
+    $cacheability_metadata->addCacheTags(['content_moderation_state_list']);
     return (bool) $this->entityTypeManager
       ->getStorage('content_moderation_state')
       ->getQuery()
diff --git a/core/modules/workflows/src/EventSubscriber/ConfigImportSubscriber.php b/core/modules/workflows/src/EventSubscriber/ConfigImportSubscriber.php
index ee2ade5..f22187f 100644
--- a/core/modules/workflows/src/EventSubscriber/ConfigImportSubscriber.php
+++ b/core/modules/workflows/src/EventSubscriber/ConfigImportSubscriber.php
@@ -2,6 +2,7 @@
 
 namespace Drupal\workflows\EventSubscriber;
 
+use Drupal\Core\Cache\CacheableMetadata;
 use Drupal\Core\Config\ConfigImporterEvent;
 use Drupal\Core\Config\ConfigImportValidateEventSubscriberBase;
 use Drupal\Core\Config\ConfigManagerInterface;
@@ -60,13 +61,13 @@ public function onConfigImporterValidate(ConfigImporterEvent $event) {
             $diff = array_diff_key($workflow_config['type_settings']['states'], $original_workflow_config['type_settings']['states']);
             foreach (array_keys($diff) as $state_id) {
               $state = $workflow->getTypePlugin()->getState($state_id);
-              if ($workflow->getTypePlugin()->workflowStateHasData($workflow, $state)) {
+              if ($workflow->getTypePlugin()->workflowStateHasData($workflow, $state, new CacheableMetadata())) {
                 $event->getConfigImporter()->logError($this->t('The state @state_label is being used, but is not in the source storage.', ['@state_label' => $state->label()]));
               }
             }
           }
           if ($op === 'delete') {
-            if ($workflow->getTypePlugin()->workflowHasData($workflow)) {
+            if ($workflow->getTypePlugin()->workflowHasData($workflow,  new CacheableMetadata())) {
               $event->getConfigImporter()->logError($this->t('The workflow @workflow_label is being used, and cannot be deleted.', ['@workflow_label' => $workflow->label()]));
             }
           }
diff --git a/core/modules/workflows/src/Plugin/WorkflowTypeBase.php b/core/modules/workflows/src/Plugin/WorkflowTypeBase.php
index 32ade73..c92c4f7 100644
--- a/core/modules/workflows/src/Plugin/WorkflowTypeBase.php
+++ b/core/modules/workflows/src/Plugin/WorkflowTypeBase.php
@@ -3,6 +3,7 @@
 namespace Drupal\workflows\Plugin;
 
 use Drupal\Component\Plugin\PluginBase;
+use Drupal\Core\Cache\RefinableCacheableDependencyInterface;
 use Drupal\Core\Plugin\PluginWithFormsTrait;
 use Drupal\workflows\State;
 use Drupal\workflows\StateInterface;
@@ -46,14 +47,14 @@ public function label() {
   /**
    * {@inheritdoc}
    */
-  public function workflowHasData(WorkflowInterface $workflow) {
+  public function workflowHasData(WorkflowInterface $workflow, RefinableCacheableDependencyInterface $cacheability_metadata) {
     return FALSE;
   }
 
   /**
    * {@inheritdoc}
    */
-  public function workflowStateHasData(WorkflowInterface $workflow, StateInterface $state) {
+  public function workflowStateHasData(WorkflowInterface $workflow, StateInterface $state, RefinableCacheableDependencyInterface $cacheability_metadata) {
     return FALSE;
   }
 
diff --git a/core/modules/workflows/src/WorkflowAccessControlHandler.php b/core/modules/workflows/src/WorkflowAccessControlHandler.php
index 8cd9cb0..d09b92a 100644
--- a/core/modules/workflows/src/WorkflowAccessControlHandler.php
+++ b/core/modules/workflows/src/WorkflowAccessControlHandler.php
@@ -3,6 +3,7 @@
 namespace Drupal\workflows;
 
 use Drupal\Component\Plugin\PluginManagerInterface;
+use Drupal\Core\Cache\CacheableMetadata;
 use Drupal\Core\Entity\EntityAccessControlHandler;
 use Drupal\Core\Entity\EntityHandlerInterface;
 use Drupal\Core\Entity\EntityInterface;
@@ -54,21 +55,25 @@ public function __construct(EntityTypeInterface $entity_type, PluginManagerInter
   protected function checkAccess(EntityInterface $entity, $operation, AccountInterface $account) {
     /** @var \Drupal\workflows\Entity\Workflow $entity */
     $workflow_type = $entity->getTypePlugin();
+    $workflow_has_data_cacheability = new CacheableMetadata();
     if (strpos($operation, 'delete-state') === 0) {
       list(, $state_id) = explode(':', $operation, 2);
       // Deleting a state is editing a workflow, but also we should forbid
       // access if there is only one state, if the state is a required state or
       // that state has data associated with it.
-      return AccessResult::allowedIf(count($workflow_type->getStates()) > 1)
+      $access_result = AccessResult::allowedIf(count($workflow_type->getStates()) > 1)
         ->andIf(parent::checkAccess($entity, 'edit', $account))
         ->andIf(AccessResult::allowedIf(!in_array($state_id, $workflow_type->getRequiredStates(), TRUE)))
-        ->andIf(AccessResult::allowedIf(!$workflow_type->workflowStateHasData($entity, $workflow_type->getState($state_id))))
+        ->andIf(AccessResult::allowedIf(!$workflow_type->workflowStateHasData($entity, $workflow_type->getState($state_id), $workflow_has_data_cacheability)))
         ->addCacheableDependency($entity);
     }
-    if ($operation === 'delete' && $workflow_type->workflowHasData($entity)) {
-      return AccessResult::neutral();
+    else if ($operation === 'delete' && $workflow_type->workflowHasData($entity, $workflow_has_data_cacheability)) {
+      $access_result = AccessResult::neutral();
     }
-    return parent::checkAccess($entity, $operation, $account);
+    else {
+      $access_result = parent::checkAccess($entity, $operation, $account);
+    }
+    return $access_result->addCacheableDependency($workflow_has_data_cacheability);
   }
 
   /**
diff --git a/core/modules/workflows/src/WorkflowTypeInterface.php b/core/modules/workflows/src/WorkflowTypeInterface.php
index 090b20f..afc457c 100644
--- a/core/modules/workflows/src/WorkflowTypeInterface.php
+++ b/core/modules/workflows/src/WorkflowTypeInterface.php
@@ -4,6 +4,7 @@
 
 use Drupal\Component\Plugin\ConfigurablePluginInterface;
 use Drupal\Component\Plugin\DerivativeInspectionInterface;
+use Drupal\Core\Cache\RefinableCacheableDependencyInterface;
 use Drupal\Core\Plugin\PluginWithFormsInterface;
 
 /**
@@ -29,13 +30,16 @@ public function label();
    *
    * @param \Drupal\workflows\WorkflowInterface $workflow
    *   The workflow to check.
+   * @param \Drupal\Core\Cache\RefinableCacheableDependencyInterface $cacheability_metadata
+   *   An object which should be used to specify the cacheability metadata used
+   *   to perform the check.
    *
    * @return bool
    *   TRUE if the workflow is being used, FALSE if not.
    *
    * @see \Drupal\workflows\EventSubscriber\ConfigImportSubscriber
    */
-  public function workflowHasData(WorkflowInterface $workflow);
+  public function workflowHasData(WorkflowInterface $workflow, RefinableCacheableDependencyInterface $cacheability_metadata);
 
   /**
    * Determines if the workflow state has data associated with it.
@@ -44,13 +48,16 @@ public function workflowHasData(WorkflowInterface $workflow);
    *   The workflow to check.
    * @param \Drupal\workflows\StateInterface $state
    *   The workflow state to check.
+   * @param \Drupal\Core\Cache\RefinableCacheableDependencyInterface $cacheability_metadata
+   *   An object which should be used to specify the cacheability metadata used
+   *   to perform the check.
    *
    * @return bool
    *   TRUE if the workflow state is being used, FALSE if not.
    *
    * @see \Drupal\workflows\EventSubscriber\ConfigImportSubscriber
    */
-  public function workflowStateHasData(WorkflowInterface $workflow, StateInterface $state);
+  public function workflowStateHasData(WorkflowInterface $workflow, StateInterface $state, RefinableCacheableDependencyInterface $cacheability_metadata);
 
   /**
    * Gets the initial state for the workflow.
diff --git a/core/modules/workflows/tests/modules/workflow_type_test/src/Plugin/WorkflowType/HasDataTestType.php b/core/modules/workflows/tests/modules/workflow_type_test/src/Plugin/WorkflowType/HasDataTestType.php
index f9774b4..4ff4858 100644
--- a/core/modules/workflows/tests/modules/workflow_type_test/src/Plugin/WorkflowType/HasDataTestType.php
+++ b/core/modules/workflows/tests/modules/workflow_type_test/src/Plugin/WorkflowType/HasDataTestType.php
@@ -2,6 +2,7 @@
 
 namespace Drupal\workflow_type_test\Plugin\WorkflowType;
 
+use Drupal\Core\Cache\RefinableCacheableDependencyInterface;
 use Drupal\workflows\Plugin\WorkflowTypeBase;
 use Drupal\workflows\StateInterface;
 use Drupal\workflows\WorkflowInterface;
@@ -19,16 +20,18 @@ class HasDataTestType extends WorkflowTypeBase {
   /**
    * {@inheritdoc}
    */
-  public function workflowHasData(WorkflowInterface $workflow) {
+  public function workflowHasData(WorkflowInterface $workflow, RefinableCacheableDependencyInterface $cacheability_metadata) {
     $workflows_with_data = \Drupal::state()->get('workflows.workflows_with_data');
+    $cacheability_metadata->addCacheTags(['workflow_data_tag']);
     return !empty($workflows_with_data[$workflow->id()]);
   }
 
   /**
    * {@inheritdoc}
    */
-  public function workflowStateHasData(WorkflowInterface $workflow, StateInterface $state) {
+  public function workflowStateHasData(WorkflowInterface $workflow, StateInterface $state, RefinableCacheableDependencyInterface $cacheability_metadata) {
     $states_with_data = \Drupal::state()->get('workflows.workflow_states_with_data');
+    $cacheability_metadata->addCacheTags(['state_data_tag']);
     return !empty($states_with_data[$workflow->id() . ':' . $state->id()]);
   }
 
diff --git a/core/modules/workflows/tests/src/Kernel/WorkflowAccessControlHandlerTest.php b/core/modules/workflows/tests/src/Kernel/WorkflowAccessControlHandlerTest.php
index 2d97a50..d2d2b9c 100644
--- a/core/modules/workflows/tests/src/Kernel/WorkflowAccessControlHandlerTest.php
+++ b/core/modules/workflows/tests/src/Kernel/WorkflowAccessControlHandlerTest.php
@@ -155,13 +155,15 @@ public function checkAccessProvider() {
         'test_workflow',
         'adminUser',
         'delete',
-        AccessResult::allowed()->addCacheContexts(['user.permissions']),
+        AccessResult::allowed()
+          ->addCacheContexts(['user.permissions'])
+          ->addCacheTags(['workflow_data_tag']),
       ],
       'Admin delete only state' => [
         'test_workflow',
         'adminUser',
         'delete-state:foo',
-        AccessResult::neutral()->addCacheTags(['config:workflows.workflow.test_workflow']),
+        AccessResult::neutral()->addCacheTags(['config:workflows.workflow.test_workflow', 'state_data_tag']),
         ['foo' => FALSE],
       ],
       'Admin delete one of two states' => [
@@ -169,7 +171,7 @@ public function checkAccessProvider() {
         'adminUser',
         'delete-state:foo',
         AccessResult::allowed()
-          ->addCacheTags(['config:workflows.workflow.test_workflow'])
+          ->addCacheTags(['config:workflows.workflow.test_workflow', 'state_data_tag'])
           ->addCacheContexts(['user.permissions']),
         ['foo' => FALSE, 'bar' => FALSE],
       ],
@@ -178,7 +180,7 @@ public function checkAccessProvider() {
         'adminUser',
         'delete-state:foo',
         AccessResult::allowed()
-          ->addCacheTags(['config:workflows.workflow.test_workflow'])
+          ->addCacheTags(['config:workflows.workflow.test_workflow', 'state_data_tag'])
           ->addCacheContexts(['user.permissions']),
         ['foo' => TRUE, 'bar' => FALSE],
       ],
@@ -204,13 +206,14 @@ public function checkAccessProvider() {
         'delete',
         AccessResult::neutral()
           ->addCacheContexts(['user.permissions'])
+          ->addCacheTags(['workflow_data_tag'])
           ->setReason("The 'administer workflows' permission is required."),
       ],
       'User delete only state' => [
         'test_workflow',
         'user',
         'delete-state:foo',
-        AccessResult::neutral()->addCacheTags(['config:workflows.workflow.test_workflow']),
+        AccessResult::neutral()->addCacheTags(['config:workflows.workflow.test_workflow', 'state_data_tag']),
         ['foo' => FALSE],
       ],
       'User delete one of two states' => [
@@ -218,7 +221,7 @@ public function checkAccessProvider() {
         'user',
         'delete-state:foo',
         AccessResult::neutral()
-          ->addCacheTags(['config:workflows.workflow.test_workflow'])
+          ->addCacheTags(['config:workflows.workflow.test_workflow', 'state_data_tag'])
           ->addCacheContexts(['user.permissions'])
           ->setReason("The 'administer workflows' permission is required."),
         ['foo' => FALSE, 'bar' => FALSE],
@@ -228,7 +231,7 @@ public function checkAccessProvider() {
         'user',
         'delete-state:foo',
         AccessResult::neutral()
-          ->addCacheTags(['config:workflows.workflow.test_workflow'])
+          ->addCacheTags(['config:workflows.workflow.test_workflow', 'state_data_tag'])
           ->addCacheContexts(['user.permissions'])
           ->setReason("The 'administer workflows' permission is required."),
         ['foo' => TRUE, 'bar' => FALSE],
@@ -238,8 +241,7 @@ public function checkAccessProvider() {
         'adminUser',
         'delete-state:with_data',
         AccessResult::neutral()
-          ->addCacheTags(['config:workflows.workflow.with_data'])
-          ->addCacheContexts([]), // @todo, should these be uncacheable?
+          ->addCacheTags(['config:workflows.workflow.with_data', 'state_data_tag']),
         ['with_data' => FALSE],
       ],
       'Admin cannot delete workflow with data' => [
@@ -247,8 +249,7 @@ public function checkAccessProvider() {
         'adminUser',
         'delete',
         AccessResult::neutral()
-          ->addCacheTags([])
-          ->addCacheContexts([]), // @todo, should these be uncacheable?
+          ->addCacheTags(['workflow_data_tag']),
         ['foo' => FALSE],
       ],
       'Admin can update workflow with data' => [