Según el baterista Will Champion en un correo en respuesta a sus seguidores, «Lost!» se empezó a componer mucho antes de que comenzaran a grabar su cuarto álbum de estudio, pero no se terminó. Fue compuesta desde cero: «Estaba probando un método particular de programación de batería. Estaba jugando con eso hasta que creé este ritmo desde cero. [...] Luego Chris [Martin] le echó un vistazo y tocó “Lost!” sobre él».^[1]​

«Lost!» fue una de las primeras canciones que la banda preparó para el álbum. Coldplay confesó que «Sing», de la banda inglesa de rock alternativo Blur, perteneciente a su álbum debut de 1991 Leisure, fue una fuente de inspiración que marcó el comienzo del proceso de composición. Durante un concierto en Detroit, Míchigan, la banda escuchó «Sing» mientras estaba en su camarín. Una vez que salieron para realizar pruebas de sonido, pensaron en escribir una canción basada en la de Blur.^[2]​ Según el guitarrista Jon Buckland: «Grabamos una parte en una iglesia que ahora es un estudio, en una enorme habitación, tocando el órgano y el piano a la vez».^[3]​ En una entrevista con The Sun, Martin afirmó: «Toda la canción surgió del verso Just because I'm losing doesn't mean I'm lost (“Sólo porque esté perdiendo no significa que esté perdido”). [...] Estábamos deprimidos al final de la última gira, [y cuando] surgió fue [como si dijéramos]: “OK, así nos sentimos. Sabemos que nos pondremos mejor”».^[4]​ El tema básico fue dando lugar a diferentes versiones.^[1]​

La canción presenta un riff de órgano, un ritmo de tambores tribales y aplausos minimalista. Hacia el final del tema, se escucha un solo de guitarra «rítmicamente creciente y similar a [los de] The Edge».^[5]​^[6]​ El uso de instrumentos «exóticos» para la mayoría de las pistas del disco, entre las que se incluye «Lost!» es resultado de querer presentar las canciones de forma diferente, algo que «no se haya escuchado» en lanzamientos anteriores.^[7]​^[8]​ En su reseña, Alex Denney de The Guardian, describió «Lost!» como una mezcla de góspel y hip hop con tablas.^[9]​ Kitty Empire de la misma publicación comentó en una reseña que «Lost!», «una genial melodía conducida por el órgano, viva con sus aplausos y patadas al piso», es el homenaje más evidente a la banda canadiense Arcade Fire entre otras pistas del disco.^[10]​

Según Chris Willman de Entertainment Weekly, la letra de «Lost!» es «un lamento sobre el despojo espiritual».^[11]​ El crítico Will Hermes de Rolling Stone dijo que la letra de la canción trata sobre «continuar contra viento y marea [y] posee la grandiosidad de “I Still Haven't Found What I'm Looking For”», una canción de la banda irlandesa U2 perteneciente a su álbum de 1987 The Joshua Tree.^[5]​ Ian Young, de la BBC comentó que se trata de «un típico estribillo de Chris Martin que combina inseguridad con determinación».^[12]​

Las siguientes son distintas variaciones oficiales de «Lost!»:

• «Lost?» es una versión acústica, que presenta solamente a la voz de Chris Martin con un acompañamiento de piano. Se la lanzó inicialmente como lado B de «Violet Hill»,^[13]​ más tarde como pista adicional de la edición japonesa de Viva la Vida or Death and All His Friends en descarga digital,^[14]​ así como también en el EP digital Lost!.^[15]​

• «Lost+» presenta una sección de rap interpretada por Jay-Z, con quien la banda grabó esta variación en Nueva York.^[16]​ Se transmitió por primera vez en la BBC Radio 1 el 16 de octubre de 2008.^[17]​^[18]​ «Lost+» se lanzó como el tema principal de dicho EP y también se lo incluyó en Prospekt's March.^[16]​^[18]​ El segmento de rap se basó en una interpretación de freestyle que cantó durante una presentación de Funkmaster Flex en la estación de radio Hot 97. Esto tuvo lugar el 31 de octubre de 2006, cuando Jay-Z se encontraba promocionando su álbum Kingdom Come.^[19]​ Coldplay la interpretó en la edición de 2009 de los premios Grammy. La interpretación comenzó con el vocalista tocando en el piano un acompañamiento como el de «Lost?», pero luego Jay-Z se unió a Martin en el escenario, cantando su parte.^[20]​

• «Lost@» es una versión interpretada en directo en el United Center, Chicago el 22 de julio de 2008.^[21]​ También se incluye en el EP.^[15]​

• «Lost-» es una versión instrumental en piano, presente en los sencillos promocionales lanzados en Europa y Estados Unidos.^[22]​^[23]​

«Lost!» se lanzó como sencillo promocional en CD en septiembre de 2008. El 10 de noviembre, Coldplay puso a la venta oficialmente un EP con cuatro versiones del tema.^[1]​^[24]​

Tuvo una recepción positiva entre los críticos. Will Hermes de Rolling Stone comentó que «probablemente», «Lost!» es «uno de los momentos pop más sublimes del álbum».^[5]​ El crítico de NME Mark Beaumont tuvo una opinión similar a la de Hermes, completando: «No es hasta [“Lost!”] —el ritmo funk del órgano, los aplausos ruidosos y Chris haciendo pucheros como un predicador en un jacuzzi lleno de strippers— que [el álbum] realmente va sobre ruedas».^[25]​ Chris Jones, de la BBC comentó: «“Lost!” parece exhibir bongós en su mezcla, aunque es [la] lastimera voz [de Martin] con su impreciso sentido de arrepentimiento, los alzamientos de acordes menores de piano explorando hacia el infinito y bombeante rock, además de un estridente optimismo lo que hará que la gente quiera acercarse a ella».^[26]​ Ryan Dombal de Pitchfork Media coincidió con Jones: «Debido a esa percusión exótica que no sonaría fuera de lugar en los LP de Peter Gabriel de antaño, “Lost!” pasa de ser “sólo otra canción de Coldplay” a una ruptura atractiva y sin igual establecida para los años que vendrán».^[7]​ Un artículo de The Guardian la criticó duramente: «Esta canción es un globo desinflado o, dicho de otra forma, un condón vacío y usado. [Chris Martin] ha mezclado [elementos] visuales, auditivos y textuales en una especie de improvisación polisensorial».^[27]​ En cuanto a su desempeño en las listas de éxitos, llegó al puesto número 54 de la UK Singles Chart en el Reino Unido.^[28]​ En los Estados Unidos llegó al puesto 87 en el Billboard Hot 100.^[29]​ Además, llegó al décimo lugar de la lista Billboard Hot Modern Rock Tracks.^[30]​

Debido al éxito del grupo en su presentación del tema en la edición de 2009 de los premios Grammy, esta interpretación junto a Jay-Z se lanzó exclusivamente por iTunes. Como resultado, «Lost+» obtuvo una nueva posición máxima en el Billboard Hot 100, reingresando en el número 40.^[29]​^[31]​ Billboard comentó sobre la colaboración: «[Posee una] brillante instrumentación con una serie de tambores y aplausos que se adaptan perfectamente al contenido lírico de la canción y hace que la transición del canto de Martin y la parte de Jay sea menos forzada».^[32]​

El video promocional para «Lost!» se lanzó oficialmente en el sitio web oficial de Coldplay el 26 de septiembre de 2008.^[33]​ Se trata de una interpretación en directo del tema en el United Center de Chicago, Illinois.^[34]​ Fue filmado y dirigido por Mat Whitecross.^[1]​ Según Luke Lewis de NME, el video es un tributo al documental de la gira de U2 Rattle and Hum.^[35]​ Se creó una versión alternativa para «Lost+». Esta es similar al original, pero la angulación de la cámara está ligeramente alterada y se muestra una pantalla de televisión en el escenario donde se ve a Jay-Z. Este último efecto se añadió en forma digital.^[34]​

Coldplay organizó un concurso en octubre de 2008 en el cual los fanes debían subir videos caseros para la versión acústica «Lost?».^[36]​ Pensada para seguidores de todas partes del mundo, finalmente acabó el 1 de diciembre de ese año.^[37]​ Cada integrante del grupo eligió los finalistas y seleccionó a los ganadores el día 5.^[38]​ El premio consistió en un par de entradas «VIP» para los recitales de la banda en Londres en diciembre de 2008 y autorización para ver los bastidores.^[36]​ Finalmente, se anunció el video ganador el 8 de diciembre, hecho por Paul O'Brien, autor de «una maravillosa combinación de animación con arcilla y gráficos computarizados». El video de O'Brien y el de Martin Buzora, quien salió en segundo lugar, están presentes en el sitio de Coldplay.^[39]​

• Página oficial de Coldplay