The album was backed by an extensive tour in Europe and North America during the summer and autumn of 1999, which was Waits' first proper tour since 1987. Other promotional stops included a solo performance on VH1 Storytellers.
Upon its release, Mule Variations received positive critical acclaim. Allmusic reviewer Stephen Thomas Erlewine stated that "the album uses the ragged cacophony of Bone Machine as a starting point, and proceeds to bring in the songwriterly aspects of Rain Dogs, along with its affection for backstreet and backwoods blues, plus a hint of the beatnik qualities of Swordfish. So Mule Variations delivers what fans want, in terms of both songs and sonics" and awarded the album four out of five stars. Former Village Voice editor Robert Christgau gave the album an A– rating and praised Waits and Brennan's songwriting, saying "together they humanize the percussion-battered Bone Machine sound, reconstituting his '80s alienation effects into a Delta harshness with more give to it."David Browne of Entertainment Weekly said that Mule Variations "restores the wizened humanity — and a more traditional sense of songcraft — to [Waits'] music," gave the album a B+ rating and concluded that Waits was "the last of the classic American tunesmiths."Hot Press reviewer Peter Murphy described the album as "an emotionally forthright record" and called it "a record of at least two minds: scuffed rooming-house madrigals [...] contrasted with big, fat, bleeding heart ballads." Zach Hooker of Pitchfork Media awarded the album a 9.5 out of 10 rating, described it as "a great album" and further described that "sonically, it picks up where Bone Machine left off, but drops some of that album's artifice: the clattering, trebly out-back-of-the-shed sound is still here and the inexplicable presence of Primus persists."Rolling Stone said that the album "contains the most blues of any album [Tom Waits has] made" but added "the problem is that it's more of the same", describing it as "the latest installment of discourse," awarding the album three out of five stars.