Група "Gov t Mule" стартувала в 1994 році як сайд-проект "Allman Brothers Band", коли двом "братам", Уоррену Хейнс (вокал, гітара) і Аллену Вуді (бас), нічим було зайнятися в основній команді. Оскільки обидва тяжіли до формату пауер-тріо типу "Cream", "Jimi Hendrix Experience" і "James Gang", то музиканти обмежилися запрошенням у свою компанію барабанщика Метта Абтс.
Дебютна платівка "Gov t Mule" була записана за принципом live-in-studio і носила яскраво виражений джемовий характер. Серед дванадцяти композицій, які були присутні на диску, виділялися дві речі: що стала концертним фаворитом "Mule" і згодом узята на озброєння "Allman Brothers Band" "Rockin Horse". За першим альбомом послідував "Live At Roseland Ballroom", а коли Хейнс і Вуді усвідомили, що "ABB" не збираються записувати новий матеріал, то зосередилися на своєму новому проекті.
У 1997-му "мули" знову засіли у студії, в результаті чого на світ з'явився опус під назвою "Dose", що вийшов набагато похмурішим, ніж дебют. Два треки ("Thelonius Beck" і "Birth Of The Mule") були присвячені видатним джазменам Телоніуса Монка і Майлза Девіса, а, крім того, робота включала в себе композицію "She Said, She Said" авторства Леннона-МакКартні.
Напередодні нового року "Gov t Mule" записали подвійний концертний альбом "Live ... With A Little Help From Our Friends". Як випливало з назви, на сцені крім основної трійці виступала купа гостей, серед яких перебували такі особистості як Марк Форд, Дерек Тракс, Берні Уоррелл і Джиммі Херрінг. У лютому 2000-го у світ вийшов альбом "Life Before Insanity", що викликав безліч захоплень серед критиків. Багато хто визнав його кращою роботою "мулів", однак для Аллена вона стала останньою. 26 серпня того ж року Вуді був знайдений мертвим в одному з номерів нью-йоркського готелю. На згадку про померлого товариша група відіграла концерт "One For Woody" і хотіла згорнути свою діяльність, але потім Уоррен і Метт передумали.
У 2001-му році музиканти організували сесії за участю запрошених басистів, за підсумками яких були випущені дві частини під назвою "The Deep End". Серед гостей значилося чимало зоряних імен, як то: Джек Брюс, Джон Енвістл, Флі, Роджер Гловер, Ліс Клейпул, Тоні Левін, Кріс Сквайр, Філ Леш, Джейсон Ньюстед і багато інших. Процес запису відобразили на плівку, і в 2003-му році вийшов документальний фільм "Rising Low".
У тому ж 2003-му "Gov t Mule" виступили на публіці з низкою учасників проекту "The Deep End", і за підсумками заходу вийшов подвійний концертний альбом "The Deepest End, Live In Concert", доступний також у форматі DVD. У супутньому турне "мули" використовували безліч найманих клавішників і басистів, двоє з яких (Енді Луїс і Денні Хесс) стали згодом офіційними учасниками команди. Студійний дебют новачків відбувся на альбомі "Deja Voodoo", що відрізнявся від попередників тим, що матеріал з нього не обкатувався заздалегідь на публіці. Частина треків не увійшла на основний реліз, тому навздогін "мули" випустили EP "Mo Voodoo".
У 2006-му шанувальники "Gov t Mule" змогли ознайомитися з дюжиною нових треків, об'єднаних на диску "High & Mighty", а в 2007-му група пішла від блюзових коренів, переробивши свої класичні речі на кшталт реггі в альбомі "Mighty High" . У тому ж році з приводу Хеллоуїна команда дала концерт, на якому зіграла "цеппеліновскій" "Houses Of The Holy". За підсумками виступу лімітованим тиражем вийшов подвійний лайв "The Haunted Holy House".