Brand New Orleans was first streamed in the Glam Slam VIP room of the NPG Music Club within 24 hours of its recording in response to Hurricane Katrina's destruction of New Orleans, Louisiana. Two days later, the song was offered as a download bundle with S.S.T. and Mavis Staples' You Will Be Moved. Eight weeks later, the track was included on the CD single of S.S.T..
Basic tracking took place on 2 September 2005 at Paisley Park Studios in Chanhassen, Minnesota, based around the final instrumental section of S.S.T., which was recorded at the same session.