diff --git a/Lib/test/test_threading.py b/Lib/test/test_threading.py
index 86f5773..639e42b 100644
--- a/Lib/test/test_threading.py
+++ b/Lib/test/test_threading.py
@@ -221,6 +221,25 @@
             t.join()
         # else the thread is still running, and we have no way to kill it
 
+    def test_limbo_cleanup(self):
+        # Issue 7481: Failure to start thread should cleanup the limbo map.
+        def fail_new_thread(*args):
+            raise threading.ThreadError()
+        _start_new_thread = threading._start_new_thread
+        threading._start_new_thread = fail_new_thread
+        try:
+            t = threading.Thread(target=lambda: None)
+            try:
+                t.start()
+                assert False
+            except threading.ThreadError:
+                self.assertFalse(
+                    t in threading._limbo,
+                    "Failed to cleanup _limbo map on failure of Thread.start()."
+                )
+        finally:
+            threading._start_new_thread = _start_new_thread
+
     def test_finalize_runnning_thread(self):
         # Issue 1402: the PyGILState_Ensure / _Release functions may be called
         # very late on python exit: on deallocation of a running thread for
diff --git a/Lib/threading.py b/Lib/threading.py
index 4bb0182..c996f42 100644
--- a/Lib/threading.py
+++ b/Lib/threading.py
@@ -455,7 +455,12 @@
             self._note("%s.start(): starting thread", self)
         with _active_limbo_lock:
             _limbo[self] = self
-        _start_new_thread(self._bootstrap, ())
+        try:
+            _start_new_thread(self._bootstrap, ())
+        except Exception:
+            with _active_limbo_lock:
+                del _limbo[self]
+            raise
         self._started.wait()
 
     def run(self):
diff --git a/Misc/NEWS b/Misc/NEWS
index d53bcb4..60603c0 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -332,6 +332,9 @@
 - Issue #7066: archive_util.make_archive now restores the cwd if an error is
   raised. Initial patch by Ezio Melotti.
 
+- Issue #7481: When a threading.Thread failed to start it would leave the
+  instance stuck in initial state and present in threading.enumerate().
+
 Extension Modules
 -----------------