The album received a mixed critical reception, though it generally tends towards the favourable. Robert Christgau gave it an A- rating and wrote "this is where Norman Cook achieves the nonstop stupidity breakbeats alone could never bring him", calling it "All shallow, all pure as a result—pure escape, pure delight, and, as the cavalcade of gospel postures at the end makes clear, pure spiritual yearning. Transcendence, we all want it."The A.V. Club called it "a big load of disposable fun and funk that's fluffier than cotton candy and just as weighty."
On the other hand, Pitchfork wrote "After enjoying a few years of relative popularity, it seems big-beat's appeal and relevance are waning. [...] After listening to Slim's latest, Halfway Between the Gutter and the Stars, it seems we've reached come-down time. And surprise! It's no fun at all", though "the problem lies more with the everchanging landscape of electronic music and the dying big-beat genre than it does with his technical skill."Entertainment Weekly called it "Melodically repetitive, the songs only intermittently approach the energizing highs of earlier Fatboy cuts."Spin called it a "post-masterpiece puzzler where the kicks just keep getting harder to find, spread-eagle between pop limitations and artistic aspirations."Piero Scaruffi called it "a mere repetition of Fatboy Slim's stereotypes. Whether tackling soul (Demons and Love Life, with Macy Gray on vocals), disco-music (Retox), dub (Song For Shelter) or funk (Talkin' About My Baby), he merely reenacts his own career. The fun is gone and the time for nostalgic reminescing has come."
^Melody Maker (11/14/00, p.51) – 4 stars out of 5 – "...Dares to go out on a potential lethal limb....Old-skool Fatboy fans will lap up the gritty, Prodigy-esque 'Yo Mama' and the kooky, slap-happy beats of 'Weapon of Choice'..."
^Muzik (11/00, p.83) – 5 out of 5 – "... Deeper and more introspective....Both thumping and atmospheric, every groove is permeated with a warm glow..."