Several official versions of the song exist, including vocalist Chris Martin's separate recording with a piano accompaniment (known as "Lost?") which appears as a B-side for "Violet Hill", and a version that features Jay-Z (known as "Lost+") which appears on their 2008 EP Prospekt's March. The accompanying music video to the single features a live performance of the band in the United States. Coldplay launched a contest through their website, in which fans submitted self-made music videos. The winning entries were posted on the band's website.
According to Coldplay drummer Will Champion in a fan mailout, "Lost!" had been developed long before the band began recording tracks for their fourth studio album, Viva la Vida or Death and All His Friends, and was not getting into completion. Champion recalls, "I was starting to get into using a particular drum programming programme. I was messing around with that and I built this beat up from scratch. ... Then Chris overheard it and played 'Lost!' over the top of it." Martin revealed that the song's drumbeat took inspiration from Justin Timberlake's "Cry Me a River", which was one of Champion's favorite songs at that time.
"Lost!" was one of the earliest songs the band worked on for the album. Coldplay revealed that "Sing" (a track off Blur's 1991 debut album Leisure) was a source of inspiration in having provided a starting point for writing "Lost!". While in Detroit, Michigan, for a concert tour, the band was listening to "Sing" in their dressing room. Once they went on stage for a soundcheck, they thought of writing a song based from it. According to guitarist Jonny Buckland, "We recorded some of it in a church up the road that's now a studio. In a huge room with a piano and organ going at the same time." In an interview with The Sun, Martin said, "The line in this song 'Just because I'm losing doesn't mean I'm lost' is what the whole record came out of because we were feeling down at the end of the last tour. That line arrived and it was, 'OK, that's how we kinda feel. We know we can improve." The ensuing track evolved in different versions.
The song's musicscape features a church organriff, tribal drum-circle groove, and minimal handclaps. Towards the end of the track, it builds into a "rhythmically soaring, Edge-like" guitar solo. Coldplay's use of "exotic" instruments for majority of tracks in the album, including "Lost!", was a result of a goal in wanting to present their songs differently, something "which have never been heard" in previous releases. In a review Alex Denney of The Guardian, he described the music of "Lost!" as "tabla-assisted gospel-hop".Kitty Empire of The Guardian wrote in a review that "Lost!", "a great organ-driven tune, alive with handclaps and foot-stomps", is the most obvious homage to Canadian indie rock band Arcade Fire among other tracks off the album.
Coldplay performed the song at the 2009 Grammy Awards. They opened it with a rendition of "Lost?" but Jay-Z joined singer Chris Martin on stage and rapped over the piano solo. This version is also referred to as "Lost+" by the website and was released digitally.
"Lost-" is an instrumental track, identical to "Lost!" but without vocals.
"Lost@" is a recording of the song performed live at the United Center, Chicago on 22 July 2008. This version also forms the basis for the single's music video.
"Lost!" was released as a promotional CD single in September 2008. On 10 November 2008, Coldplay officially released a four-track digital EP of "Lost!", confirming the song's status as a single.
The song has been well received by critics. Will Hermes of Rolling Stone magazine noted "Lost!" as "probably" the "album's most sublime pop moment".NME's critic Mark Beaumont had the same view of Hermes, complimenting, "It's not until ['Lost!'] – all church organ funkiness, stomporific handclap rhythms and Chris pouting like a preacher in a jacuzzi full of strippers – that [Viva la Vida] really hits its stride." Chris Jones of BBC writes, "... 'Lost!' seems to sport bongos in its mix, yet it's the plaintive voice with its vague sense of regret, the lifts from minor key piano forays into vast, pumping rock and also a strident optimism that people are going to come here for." Ryan Dombal of Pitchfork Media had the same sentiment: "Thanks to a bubbling bit of exotic percussion that wouldn't sound out of place on Peter Gabriel's latter-day LPs, 'Lost!' is transformed from Just Another Coldplay Song into a uniquely alluring smash and live staple for years to come." An article in The Guardian lambasted "Lost!": "This song is a deflated balloon, or, put another way, a used empty condom. He has, I think, merged visual, audio and textual into a kind of polysensory jam; no part of it works without the other two."
Since it did not match the commercial success of the album's previous singles, "Lost!" charted in some countries during the week of the album being released and due to high digital sales, despite not officially being a single at the time. It has charted most notably the United Kingdom where it peaked at number 54 in the UK Singles Chart and in the United States where it debuted at number 94 on the Billboard Hot 100. The single has peaked at number 10 on the BillboardHot Modern Rock Tracks. Its UK peak made the single Coldplay's first to fail to chart in the UK Top 40 although considering the fact that it was not physically released (though it was still available as a digital download at the time).
Buoyed by the band's success at the 2009 Grammy Awards, a live Grammy performance of the single featuring Jay-Z was released exclusively to iTunes, spurring digital download sales. As a result, "Lost!" achieved a new peak position on the Billboard Hot 100, re-entering at number 40. Billboard called the collaboration a "gloomy instrumentation with a series of drums and claps that perfectly fits the lyrical content of the song and makes the transition from Martin's singing to Jay's rapping seem effortless."  Christian Hoard of Rolling Stone, in his review of Prospekt's March, praised "Lost+" as containing a "great Jay-Z cameo."
The music video to "Lost!" was officially released on Coldplay's website on 26 September 2008. It features a live performance of the song at United Center in Chicago, Illinois. It shows views of different members of the band playing the song and Chris Martin actively moving around stage while singing. The video was filmed and directed by Mat Whitecross. According to Luke Lewis of NME, the video is a tribute to U2's tour documentary Rattle and Hum. An alternative version was released for "Lost+". This video is the same as the original but with the camera angles slightly altered, primarily to show a screen on stage which features Jay-Z whose performance was added digitally.
Coldplay launched a contest in October 2008 in which fans submitted homemade music videos for the "Lost?" acoustic version. Open to all fans worldwide, the competition closed on 1 December 2008. All members of the band picked the finalists and judged the winning entries on 5 December. The winner was awarded a pair of "ultra-VIP" tickets to the band's show in O2 arena in London in December 2008, and it included backstage passes. The winning video was announced on 8 December 2008, with the winner being Paul O'Brien for a "Wonderful blend of Claymation and Computer Graphics". O'Brien's video and the runner up, made by Martin Buzora, are featured on Coldplay's official website.