Upon its release, In Search of Stoney Jackson received generally favorable reviews from music critics. At Metacritic, which assigns a normalized rating out of 100 to reviews from mainstream critics, the album received an average score of 75, based on 11 reviews. Phil Freeman of AllMusic gave the album four and a half stars out of five, saying "From a purely instrumental standpoint, this album is the equal of the Beastie Boys' Paul's Boutique, but without the recognizable hooks--every sound here is ultra-obscure and the more entertaining for it."The A.V. Club's Nathan Rabin gave the album an A–, saying "For an in-demand producer like Madlib, it might not be good business to give some of his most stunning beats to a relatively unknown group, but Jackson is brilliant enough to elevate Strong Arm Steady to the level of cult heroes." Jeremy Moehlmann of Filter gave the album 84%, saying "Solid, workmanlike rhymes abound, but a shortage of mind-blowing moments is tempered by the absence of mediocrity."Okayplayer reviewer Jeff Harvey gave the album an 84 out of 100, saying "All three MCs, particularly an energized Phil Da Agony, deliver more than their share of memorable verses, but they never quite take ownership of the record. It feels like most of the beats were selected to suite the guests, and since there are guests on nearly every track, the end result plays like a first rate Madlib mixtape hosted by Strong Arm Steady. Still, fans of SAS, Madlib, or vintage hip-hop in general will find more than enough heavy hitting beats and gensu-sharp rhymes to keep this album in rotation until Stoney Jackson is found."
HipHopDX reviewer Michael Cusenza gave the album a four out of five, saying "In Search of Stoney Jackson is another Stones Throw gem mined by their incomparable in-house Konducta. It's a funky ride to Rap's far side in a car fabricated by Madlib, commandeered by Strong Arm Steady and a slew of able narrators."Pitchfork's Patrick Sisson gave the album a 7.1 out of ten, saying "For all Madlib's eclecticism and supposedly short attention span, his work here sounds focused and sharp. The beats aren't wasted here by any means, but a different crew could have brought out even more potential." Mosi Reeves of Spin gave the album a seven out of ten, saying "With Strong Arm Steady's MC trio of Krondon, Phil Da Agony, and Mitchy Slick (plus extended fam like Planet Asia, Phonte, and Fashawn) dropping lyrical barbs ("Telegram") and creatively reheated thug-isms ("Needle in the Haystack"), Madlib chops up loops bubbling with quirky humor and analog soul." Matt Jost of RapReviews gave the album a seven out of ten, saying "It doesn't sound like much upon first listen. But after a few spins In Search of Stoney Jackson becomes a charming little record that has quite a lot to offer despite its fragmented, uncoordinated appearance." Joe Schmoh of Sputnikmusic gave the album three and a half stars out of five, saying "That disappointment resonating from the main attraction quickly boils over, as the guests and Madlib's tasteful samples give In Search of Stoney Jackson a [sic] off-the-cuff, mixtape-ish feeling that makes it truly a fun listen. Madlib still proves he's the master of his terrain, and certain guests slay their hosts, but for the most part, it's a mix of 90s nostalgia and the new kids, and fits together perfectly."
In a mixed review, B. McGhee of Tiny Mix Tapes gave the album a three out of five, saying "These songs are alive, but there are too many cooks, and they clutter things with all their different ideas and approaches. Madlib's instrumental interludes are weird and compelling, which is no surprise, but because of the multitude of voices, his influence is more subdued than usual."PopMatters reviewer David Amidon gave the album a six out ten, saying "Stoney Jackson isn't an album with big expectations, but as a result it fails to disappoint as well. After an incredibly strong start Stoney Jackson assumes its role as a modest, strong ringing in of the hip-hop new year, and I for one am fine with that." Ben Yaster, in his review for Dusted Magazine, wrote "Like many collaborations, the material on Stoney Jackson is varied and can feel rudderless at moments." Vyvian Raoul of Drowned in Sound gave the album a four out of ten, saying "In the end, perhaps In Search… is just so inbred it's capable of little more than frenzied tail wagging on a podium – its maniac tongue lolling – all eager and expectant that someone will pin a rosette to it just for having a nice shiny coat."