Madvillainy was praised for its unique and innovative approach to hip hop; short tracks, abstract lyrics, few choruses and a sound generally unfriendly to commercial radio. Despite this, the album achieved moderate commercial success, peaking at number 179 on the US Billboard 200, and attracted much attention from media outlets not usually covering hip hop music, including The New Yorker.
Four videos were filmed for the album: "All Caps" (directed by James Reitano), "Rhinestone Cowboy" and "Accordion" (both directed by Andrew Gura), and "Shadows of Tomorrow" (directed by System D-128). "All Caps" and "Rhinestone Cowboy" appear on the DVDStones Throw 101 along with a hidden easter egg video for "Shadows Of Tomorrow" as a hidden feature. An impromptu video for "Accordion" was filmed in 2004 but not released until 2008's In Living the True Gods DVD.
At least two tracks on Madvillainy ("Rhinestone Cowboy", "Strange Ways") were produced using a portable turntable, a cassette deck and a Boss SP303 sampler by Madlib in Brazil. The first music to be publicly debuted from Madvillainy was the song "America's Most Blunted" which was played by Madlib at the Red Bull Music Academy in Brazil, November 2002.
An instrumental version of the album was released only in vinyl format and digitally through various online stores, with the tracks "The Illest Villains", "Bistro", "Sickfit", "Do Not Fire!", and "Supervillain Theme" being omitted. Two remix EPs of Madvillainy were released on Stones Throw. The remixes were done by Four Tet and Koushik.
In 2009, the album was selected in HipHopDX.com's Top 10 Albums of the '00s.Spin (p. 66) - Ranked number 17 in Spin's 40 Best Albums of the Year - "Madlib's production — thick, woozy slabs of beatnik bass — keeps things hotter than an underground volcano lair."
Rhapsody - Ranked number 13 on Rhapsody's 100 Best Albums of the Decade list and number 1 on the Hip-Hop's Best Albums of the Decade list. "The collaboration between underground hip-hop’s most adventurous producer (Madlib) and its most treasured lyricist (MF DOOM), Madvillainy is full of dark alleys and trapdoors. DOOM’s lines are extended vocabulary workouts and take repeated listens to fully unpack, yet there are times when the emcee peers through the Dada-ist carnival of words and speaks directly and honestly. Madlib’s production, meanwhile, is pure pastiche, a smorgasbord of world music, classic soul and outsider music. Snippets of childhood recordings rub against Sun Ra and Sonny Rollins. It’s a dark, funny and strange album."
Pitchfork ranked the album at number 13 in their list of the top 100 albums of 2000-04, commenting, "While Madlib's special power played tricks on your ears-- a sample you were sure was the sound of cars rolling by on the street might sound like the hiss of a record on a different day ("Rainbows")-- Doom unfurled his clever lyrics like a roll of sod on earth... and the album curved in on itself like a two-way mirror." Pitchfork more recently ranked it as the 25th best album of the 2000s.
"All Caps" can also be found in QuickTime format when the Madvillainy disc is placed in a computer.
On The Boondocks episode titled Let's Nab Oprah, three songs from Madvillainy are used: "Raid", "All Caps", and "Strange Ways". The episode Wingmen features "Fancy Clown".
During its run, a snippet of "Do Not Fire!" was played prior to opening sequence of the hip-hop-influenced chanbara anime Samurai Champloo. The clip was played to the tune of a revolving image of the show's logo—a vinyl record—giving off the illusion of scratching.
At the end of an MTV special for the movie "V for Vendetta", the titular character interrupts the show, ending his message with "and remember, all caps when you spell the man's name."
Viktor Vaughn's anger in "Fancy Clown" is directed not only to his fictional girlfriend but to DOOM himself ("Don't make me have to pound his tin crown face in"), ("That's you if you want a dude who wears a mask all day"), an alter-ego of Vaughn himself (Daniel Dumile).
Beats for "Strange Ways" and "Rhinestone Cowboy" were partially produced in a hotel room in Brazil, late 2002.
"Rainbows" was covered by rapperMos Def and the Hypnotic Brass Ensemble at least once, during a concert soundcheck which can be seen on YouTube. "All Caps" was also covered by Mos Def and his Watermelon Syndicate orchestra at their July 2008 Carnegie Hall show. He also covered "Accordion" in a Chicago concert.