The album received generally positive reviews from critics.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."
An edited version also exists, which removes "Star 69" (due to the song's recurring use of the word "fuck", which is the sole reason for obtaining a Parental Advisory label), and removes the song's reprise used in "Song for Shelter".