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".