Train is the fifth track on Mavis Staples' first Paisley Park Records album Time Waits For No One.
Basic tracking for Prince's original version took place on 7 July 1986 at Prince's Galpin Blvd Home Studio in Chanhassen, Minnesota (the day before he recorded Eggplant and two days before he recorded It Ain't Over 'Til The Fat Lady Sings).
Prince's version was included as the third track on the 18 July 1986 configuration of the album Dream Factory. When Prince decided not to proceed with the album after disbanding the Revolution, and concentrated instead on Camille and Crystal Ball (both of which were also aborted), he decided not to include this song, even though it did not contain input from the Revolution.
Prince revised the song in late June 1988, at Paisley Park Studios in Chanhassen, Minnesota (during the same set of sessions as recording Time Waits For No One and revising Come Home and I Guess I'm Crazy). The song was then sent (along with Time Waits For No One, Come Home and I Guess I'm Crazy) to Mavis Staples in Memphis, Tennessee, where she recorded lead vocal overdubs with producers Al Bell, Homer Banks and Lester Snell at Ardent Studios.