T.I. had initially recorded "Memories Back Then", for his eighth studio album Trouble Man: Heavy Is the Head (2012). In an interview released on October 19, 2012, West Coast rapper Kendrick Lamar revealed that he recorded a song with T.I., for the aforementioned album. The song was also reported to feature B.o.B and sample Belgian-Australian singer-songwriter Gotye's hit single, "Somebody That I Used to Know". Although the track failed to appear on Trouble Man due to sample-clearance issues, B.o.B announced the song would be the first single from the Grand Hustle Records compilation album, Hustle Gang.
The song's mass appeal attracted T.I. to the sample: "The record's just jamming. When I heard the twist they put on it, man, it was kind of a no-brainer." T.I. also chose the record for its crossover ability, which he has always been successful with in the past: "It sounds like hip-hop with an international twist to it, and I'm known for taking those types of records and bridging that gap between what we do and what they do," he explained, dropping in a couple of examples. "From M.I.A.'s 'Paper Planes' to 'Swagga Like Us,' we took [Crystal Waters'] 'Gypsy Woman' for 'Why You Wanna.'"
Over the drum-heavy sample, Lamar and Bobby Ray join T.I. in sharing some nostalgic stories, which he says reminds him of some of a few renowned MCs and their classic projects: "[We're] taking turns on our story about a female that we knew years, years, years ago before we were who we are today. It kinda puts me in the mind of the 'Da Art of Storytellin' [and The Art of Storytelling] from Outkast and Slick Rick. It puts me in the mind of that." The song failed to make the album's final track listing probably due to sample clearances. On December 17, 2012 T.I. stopped by Sway Calloway's Sway in the Morning radio show to promote the album, while there he premiered "Memories Back Then".
T.I. felt the song needed to reach more people so he had the song reworked, removing the sample: "I rocked out as soon as I heard it. It felt relevant, it felt urgent. However, I was not able to work out a clearance. I didn't want to waste the opportunity because it was such a great performance and meaningful message from myself and B.o.B and Kendrick.”, T.I. said to Rap-Up.
In March 2013, T.I. filmed the music video for "Memories Back Then", in Los Angeles, California, alongside B.o.B, Kendrick Lamar and Kris Stephens. The music video for "Memories Back Then", directed by Philly Fly Boy, was released April 22, 2013.