Records officially released the song to US contemporary hit radio on June 27, 2010. A radio remix version of the track was digitally released on 7digital stores worldwide in July 2010. Two digital EPs containing remixes of the song were also distributed by RCA Records later that year. Composition "You Lost Me" was written by Aguilera, Furler and its producer, Samuel Dixon. The song is a ballad lasts for a duration of (four minutes and 17 seconds). Written in the key of A minor, "You Lost Me" has a tempo of 50 beats per minute. Aguilera's vocal range spans from E♭3 to E5. The verses are sung by Aguilera using melisma. The song's instrumentation comes from piano and strings. Hinshaw Drew of The Village Voice labelled it the "un-bionic moment on the record". Lyrically, "You Lost Me" talks about a "cheating" man, who has left Aguilera's world "infected". Amar Toor from AOL Radio thought that its lyrical content "perfectly captures one of the most difficult experiences young lovers have to go through". The song begins with a "somber orchestral" piano opening, followed by the lines "I am done, smoking gun/ We've lost it all, the love is gone" sung by Aguilera. During the chorus, she sings, "I feel like our world's been infected/ And somehow you left me neglected". Toward the ending, Aguilera's "painful" and "catharsis" voice "crescendos dramatically". According to Jon Pareles from The New York Times, Aguilera "barely" holds back her tears in the song. The Village Voice critic Drew Hinshaw thought that Aguilera is "less vexed by what he did than what he lost". Critical reception "You Lost Me" received generally positive reviews from music critics. Leah Greenblatt from Entertainment Weekly noted Furler's efforts on the "lovely" ballads "You Lost Me", "All I Need", and "I Am" had turned Aguilera into a "smoky, almost Fiona Apple-esque torch singer". She also considered the first one of them as "one of the most gorgeous things she’s [Aguilera] ever done". Elysa Gardner of USA Today highlighted the song as one of the album's standout ballads. According to Genevieve Koski from The A.V. Club, "You Lost Me" is the kind of ballad Aguilera "is best suited to". Mesfin Fekadu of Northwest Herald thought that the "emotional" song shows off "the diva's powerful voice", while Drew Hinshaw from The Village Voice deemed "You Lost Me" as the most vulnerable song from Bionic.