diff --git a/Lib/test/test_threading.py b/Lib/test/test_threading.py
index b8265aa..9e540c2 100644
--- a/Lib/test/test_threading.py
+++ b/Lib/test/test_threading.py
@@ -247,6 +247,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 0e77060..7e513b8 100644
--- a/Lib/threading.py
+++ b/Lib/threading.py
@@ -465,7 +465,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):