Upon its release, Theme for a Broken Soul received generally favorable reviews from music critics. Josh Bush of AllMusic gave the album three and a half stars out of five, saying "Madlib is surprisingly faithful here, each track sounding like it could be inserted on a broken beat mix album with few problems. Little character, to be sure, but solid results." Nikhil P. Yerawadekar of HipHopSite gave the album a three out of five, saying "This DJ Rels album, while never particularly offensive, is monotonous (most of its songs being in one narrow tempo range) and overall uninteresting. Madlib could have done a lot better than this album." Matthew Gasteier of Prefix Magazine gave the album a 6.0 out of ten, saying "Madlib often succeeds as DJ Rels, and he should be applauded for even trying to go in such a different direction. But save the applause for when you're on the dance floor. Personally, I'm staying home and putting on Madvillainy." Dan Mennella of RapReviews gave the album an eight out of ten, saying "When you're as well accomplished as Madlib is, you've earned the right to try something a little different like this. Heck, he's already made a career out of it."