diff --git a/_states/heatv1.py b/_states/heatv1.py
index 4ee8cf5..45cff84 100644
--- a/_states/heatv1.py
+++ b/_states/heatv1.py
@@ -28,6 +28,10 @@
                            name=stack_name,
                            cloud_name=cloud_name)
         if not stack["result"]:
+            if action == "DELETE" and stack['status_code'] == 404:
+                stack_status = 'DELETE COMPLETE'
+                msg = msg_template % dict(name=stack_name, status=stack_status)
+                return 'DELETE_COMPLETE', msg
             raise Exception("request for stack failed")
 
         stack = stack["body"]["stack"]