After a nine-year period dedicated to touring and working on other projects, both solo and as part of Hieroglyphics, Montezuma's Revenge marked Souls of Mischief's return as a group.

[1] In a 2011 interview with Complex magazine Prince Paul admitted he is still not fully satisfied with the end result, but thinks the album is pretty good.

[9] Montezuma's Revenge was met with generally positive reviews, with most music critics praising Prince Paul's production but highlighting the group's lack of originality.

Clayton Purdom of AllMusic called it "the opposite of a comeback – a stay-put, maybe, right back in the halcyon '90s", noting that neither Souls of Mischief nor Prince Paul changed since then, which makes Montezuma's Revenge look like a cash grab.

[15] HipHopDX's Luke Gibson wrote that Montezuma's Revenge "rightfully stands beside [the group's] first two releases", as Souls of Mischief stay true to their audience and themselves.

[11] Andrew Martin, writing for PopMatters, called the album "a slightly bloated, though almost-great record", listing occasional weak rhymes and hooks as its downsides.