When you start writing, the first batch of songs is almost always puerile ballads, for some reason - I think they're easier to write. To write a good rock and roll song is one of the hardest things because it has to be stripped down so simple, to that same basic format shared by rock & roll and rhythm & blues and Irish folk songs from thousands of years ago. It's a very simple form, and yet you have to find a certain element in there that still lives, that isn't just a rehash. It can REMIND you - and probably will - of something else, but it should still add something new, have a freshness and individuality about it. The rules on it are very strict, you see (laughs). I think The Last Time was the first one we actually managed to write with a BEAT, the first non-puerile song. It had a strong Staple Singers influence in that it came out of an old gospel song that we revamped and reworked. And I didn't actually realize until after we'd written it because we'd been listening to this Staple Singers album for 10 months or so. You don't go out of your way to LIFT songs, but what you play is eventually the product of what you've heard before.So said Keith about "The Last Time" (thanks to TimeIsOnOurSide.com for that quote).
A lot of people say that the Stones "stole" the song from the Staple Singers – Keith alludes to those charges above, and even seems to agree with them to an extent. I'm not sure how much credit needs to go to the Staples Singers, though. The Rolling Stones version of the song is a rocker from beginning to end, with an insistent guitar riff driving it. The Staples version of the song is a contemplative gospel cry, with none of the anger that made Mick's vocal so interesting. Here, listen:
Additionally, it should be noted that "Maybe the Last Time" is a traditional gospel song, performed by countless artists. Here is the first version I heard, by the Five Blind Boys of Alabama some time in the late 50s:
So even if the Stones did rip the song off to a significant degree (and they admit to taking something), it's not obvious that the Staples Singers invented whatever it was the Stones stole.
Also potentially relevant is James Brown's "This May Be the Last Time" single , which dates to sometime in 1964. (The Stones followed James Brown on the famous 1964 T.A.M.I. Show, but I don't think he performed this song.)
Recording for the Ed Sullivan Show, I think. Image courtesy of the Guitar101.com forums