diff --git a/client/task_runner.go b/client/task_runner.go
index <HASH>..<HASH> 100644
--- a/client/task_runner.go
+++ b/client/task_runner.go
@@ -1076,8 +1076,12 @@ func (r *TaskRunner) run() {
 	}
 }
 
-// cleanup calls Driver.Cleanup when a task is stopping. Errors are logged.
+// cleanup removes Consul entries and calls Driver.Cleanup when a task is
+// stopping. Errors are logged.
 func (r *TaskRunner) cleanup() {
+	// Remove from Consul
+	r.consul.RemoveTask(r.alloc.ID, r.task)
+
 	drv, err := r.createDriver()
 	if err != nil {
 		r.logger.Printf("[ERR] client: error creating driver to cleanup resources: %v", err)
@@ -1425,9 +1429,6 @@ func (r *TaskRunner) handleUpdate(update *structs.Allocation) error {
 // given limit. It returns whether the task was destroyed and the error
 // associated with the last kill attempt.
 func (r *TaskRunner) handleDestroy() (destroyed bool, err error) {
-	// Remove from Consul
-	r.consul.RemoveTask(r.alloc.ID, r.task)
-
 	// Cap the number of times we attempt to kill the task.
 	for i := 0; i < killFailureLimit; i++ {
 		if err = r.handle.Kill(); err != nil {
Move removal from Consul into TaskRunner cleanup