The album, which is built around a mix of organic instrumentation and idiosyncratic samples, was met with largely positive reviews by music critics, although it was somewhat criticised due to its near-constant mellowness.

The album was nominated for the Mercury Music Prize and Brit Award in 2003,[1] and was eventually certified gold by the British Phonographic Industry for shipments exceeding 100,000 copies.

Lost Horizons opens with "Elements", which "blends acoustic guitars, flugelhorns, synths, skittering breakbeat rhythms, a folksy harmonica, and ... a falsetto 'doo-doo' chorus".

[2] Overlaying the music is a voiceover, courtesy of English actor John Standing, that lists the basic 'elements' that make up the world: earth, metal, water, wood, fire, and (eventually, later in the song) sky.

[6] The band had initially intended to use a sample of Errol Flynn talking about his travels, but since it only included four destinations they compiled a list of 200 places and recorded Standing reading them.

Stuart Mason of AllMusic called the album "a delightful but slightly faceless blend of lounge pop, subtle beats, found sound, with mellow jazz influences.

"[13] A reviewer for Entertainment.ie praised the band for approaching electronica from a new angle, writing, "this London-based duo employ Playschool pianos, acoustic guitars and sprightly beats to create laid-back instrumentals guaranteed to soothe even the most restless of souls.

[...] What really marks Lemon Jelly as exciting new talents is their quirky sense of humour, which they use to brighten up their sound with skilful use of nursery rhymes, brass bands and offbeat samples.

"[21] Pascal Wyse of The Guardian wrote, "Everything is approachable and purely crafted, but Lost Horizons cheats banality with some choice quirks: Magnificent Seven strings, astronauts chatting, panoramic sound effects.

"[9] Chris Dahlen of Pitchfork felt that the album was a little too saccharine at times, but that it is "the perfect disc to throw on after your four-disc Ultrachill Dub Groove Mix has put the whole party to sleep.