Anlagt som vejforbindelse fra Kalvebod Brygge til havnebassiner, der bl.a. blev brugt af tømmerhandlere.
Den kunstigt opfyldte ø, som vejen gik ud til, opstod i begyndelsen af 1900-årene. Her holdt nogle af Københavns hjemløse til og kaldtes derfor populært for Djævleøen. Navnet fremgik dog af de officielle kort.
Senere har hele området fået navnet Enghave Brygge, som var betegnelsen for den kaj, der blev anlagt i årene efter 1. Verdenskrig. Her var især faciliteter til kulfirmaer.
I midten af 1960’erne blev Tømmergravsgades nordlige del gjort til blind vej, og udkørslen til Vasbygade kom i stedet til at gå ad den korte gade Kortløb.
Tømmergravsgade er i dag næsten forsvundet som vejnavn, idet det meste af vejen i 2016 har skiftet navn til Nelson Mandelas Allé.
Københavns Roklub er en af de få, der har adresse på vejen. Klubben er grundlagt i 1866 og flyttede allerede i 1902 til Tømmergravsvej. Det nuværende klubhus (billedet herover) er fra 1941.