Baltimore was a digital single released on 26 May 2015, as a stand-alone Prince single (although the following day the Prince3EG Twitter account teased a new release, possibly titled Free Urself, with a link to the single, indicating that it might have been intended for an album using that title at a later date). Baltimore was included on Prince's 39th studio album Hitnrun Phase Two when it was released in December 2015, but this project is believed to have come later. In retrospect, however, Baltimore can be considered the album's fourth single (after Extraloveable, Rock And Roll Love Affair and Screwdriver).
The single was only made available on iTunes.
The single version of the song contained additional orchestral and muted trumpet overdubs compared with the version first streamed on the Prince3EG Soundcloud account earlier in the month.