Andre Williams & His Orchestra has been played on NTS in shows including House Call, featured first on 6 December 2015. Songs played include Sweet Little Pussycat and Soul Party A-Go Go.

He lived in a housing project with his mother until she died when he was only six years of age. Even though he was sly and was strangely smart as a young boy, his "aunties" raised Mr. Williams until he was around 16. At sixteen, Andre Williams set out on his own and moved to Detroit, Michigan. There, he became friends with Jack and Devora Brown, owners of Fortune Records which was located at the back of a barber shop.

He then became lead singer for The 5 Dollars in 1955, which already had a contract with Fortune Records. Though most of the songs were billed as Andre Williams and the Don Juans (on Epic in 1956 billed as Andre Mr Rhythm Williams and his New Group), "Bacon Fat" and "Jail Bait" were solo efforts. "Bacon Fat" hit #9 on the Billboard R&B Charts in 1957. "Bacon Fat" written as well by Andre Williams was such a success that Fortune Records sold the song to Epic Records), - Epic 5-9196 BACON FAT/JUST BECAUSE of a KISS, a much larger distributor. Since "Bacon Fat" and "Jail Bait" were such successes, Williams figured that "talking instead of singing" was a better idea for him, for he didn't have as good a voice as some other singers from the 1950s. In 1960 (rereleased in 1986 on Fortune), Fortune released a complete LP, of all of his singles with the Don Juans, which was titled Jail Bait. This was just the start of Williams' nationwide fame.

In 1960 he appeared on Motown's Miracle Record label releasing Rosa Lee.

In the early 1960s, Williams co-wrote Stevie Wonder's first song called "Thank You for Loving Me." Andre Williams' "Shake a Tail Feather" was also made a super hit in 1963 by the Five Du-Tones and again by Ike & Tina Turner. Alvin Cash & the Crawlers also made a hit out of the Williams song "Twine Time." As well as making these hits, Williams also supervised the making of 2 or more albums by The Contours. In the '60s, Andre Williams was the manager and roadie for soul singer Edwin Starr as well.

In 1966 releasing 2 records on the Avin Record Label, then 2 records were released on Detroits' Wingate label; Loose Juice & Do it. Then Ric Tic in 1967 he released; Yove Got it and I want it.

In 1968, Williams was signed to Chess Records on Checker, Chicago's major blues label. He was back…wearing velvet lavender suits and playing "bucket-of-blood" styled joints. Chess released many hits for Williams—"Humpin' Bumpin' and Thumpin'" and "Cadillac Jack" in particular. Then, he began to work with many unknown black labels and pour out songs like "Sweet Little Pussy Cat" and "Rib Tips, Pts. 1 & 2." In 1968, Williams collaborated with the Natural Bridge Bunch to release "Pig Snoots," a novelty song about a man named Ricky who would "come all way cross town to get me some snoots". In the 1970s, Williams wrote some songs for Parliament (band) and Funkadelic, two popular funk groups. (Comedian Redd Foxx then dubbed Andre Williams his most famous nickname, Mr. Rhythm). Once again, Williams began to produce cuts for Ike Turner.

Throughout the 1980s, Andre Williams was in poverty because of his drug addictions. He lived in Chicago, Illinois; at one point, he was begging for money on a Chicago bridge. Andre Williams' homelessness would forever change him.

However, this did not stop Mr. Williams' dignity. In 1996, Andre Williams released Mr. Rhythm, which featured new renditions of his old tunes from the "Jail Bait" era. Some included "The Greasy Chicken," "Mean Jean," and "Pass the Biscuits Please." It was a definite comeback for Mr. Williams, but the most of the crowd had already forgotten about him, and wanted newer-styled music.

He surely changed his style with 1998's Silky. Considered the world's sleaziest album ever, Silky revolutionized the punky style, dubbed sleaze-rock. Mark Deming speaks about Silky: It's "noise-spattered, stripped-down, roots-punk assault, and the results are flat-out nuts." Though sleaze rockers idolized Williams, most critics preferred his original style.

In 1999, he recorded a country album with The Sadies, called Red Dirt.

In 2000, Andre Williams plotted against the critics once more with The Black Godfather. The noisy, electric, fuzzy sound was back, with two songs backed by The Dirtbombs. By this time, Andre was already back on stage, performing at the "bucket-of-blood" clubs again. The Black Godfather became his new title, along with the outdated Mr. Rhythm.

In 2001 he discussed his recent conversion to Judaism and circumcision.[1]

But seeing that his albums were not musical enough for critics to praise and that he wasn't making great music anymore, Andre tried to bring back his soul with Aphrodisiac in 2006. "The result is a more laid-back and funky groove that's soulful but potent at the same time, fusing '70s blaxploitation sounds, Jimmy Smith-style jazz figures, and Booker T.-influenced R&B workouts into one solid package" is the way Mark Deming puts Aphrodisiac.

He still plays shows in the USA, and toured Europe in 2001 (with Dutch band Green Hornet as backing band), 2005 and 2006 (with the Marshall Brothers). From August to November 2006, he had a short European tour, ending in Switzerland. 2008 Feb. and Mar. European tour with The Flash Express, France, U.K. and Germany.

In 2007, Andre finished recording his latest album with the New Orleans based band, Morning 40 Federation. The album, titled Can You Deal With It, was released by Bloodshot Records in 2008 and is credited to Andre Williams & the New Orleans Hellhounds (the pseudonymous Morning 40 Federation).