diff --git a/cluster-autoscaler/cluster_autoscaler.go b/cluster-autoscaler/cluster_autoscaler.go
index <HASH>..<HASH> 100644
--- a/cluster-autoscaler/cluster_autoscaler.go
+++ b/cluster-autoscaler/cluster_autoscaler.go
@@ -240,6 +240,11 @@ func run(_ <-chan struct{}) {
 
 	scaleDown := NewScaleDown(&autoscalingContext)
 
+	// CA can die at any time. Removing taints that might have been left from the previous run.
+	if readyNodes, err := readyNodeLister.List(); err != nil {
+		cleanToBeDeleted(readyNodes, kubeClient, autoscalingContext.Recorder)
+	}
+
 	for {
 		select {
 		case <-time.After(*scanInterval):
@@ -304,9 +309,6 @@ func run(_ <-chan struct{}) {
 					continue
 				}
 
-				// CA can die at any time. Removing taints that might have been left from the previous run.
-				cleanToBeDeleted(readyNodes, kubeClient, autoscalingContext.Recorder)
-
 				allUnschedulablePods, err := unschedulablePodLister.List()
 				if err != nil {
 					glog.Errorf("Failed to list unscheduled pods: %v", err)
Cluster-autoscaler: clear to be deleted taints only at the startup