Upon its release, Most of My Heroes Still Don't Appear on No Stamp received positive reviews from music critics, who complimented its production and found its political lyrics relevant to contemporary times.
Most of My Heroes Still Don't Appear on No Stamp received generally positive reviews from music critics. Allmusic editor Stephen Thomas Erlewine gave it four out of five stars and commended Public Enemy for "remain[ing] true to the sounds and sensibilities they laid out back in the late '80s", writing that "the music remains vital and vibrant, possibly because, despite some progress, things still haven't changed all that much and, in some respects, have gotten worse...and as long as Public Enemy's heroes remain consigned to the margins, they'll still make music as dynamic as this." Ray Rahman of Entertainment Weekly complimented its production, particularly the "newer, weirder, and welcome musical elements" on certain tracks, and called the album "pretty damn great."
Consequence of Sound's Matt Melis gave the album three stars and felt that "a few cuts [are] completely out of left field", writing that "most of this record falls into tried-and-true PE formulas, but there's no dust or rust to be found on the album's top tracks."MSN Music's Robert Christgau gave it an "A–", indicating "the kind of garden-variety good record that is the great luxury of musical micromarketing and overproduction. Anyone open to its aesthetic will enjoy more than half its tracks." Christgau found it "pretty damn good" and felt that "preacher Chuck needs William Drayton's nuttiness no matter how corrupt it's become, in part because its corruption is a corrective to all of Chuck's conceptualizing." He criticized that, although the album's "young beatmakers echo the old Bomb Squad whomp, the preacher has lost some boom vocally, and like his cadences, the politics are old-school", but "the times justify those old politics more than ever."