This song about the power of redemption was written by Monty Criswell and Rick Huckaby. Criswell also co-wrote George Strait's "I Saw God Today."
Trace Adkins told The Fayetteville Observer: "'Muddy Water' is actually the first gospel song I've recorded in 10 years. It's funny because it reminds me of when I started out - singing in a gospel quartet when I was 17, almost 30 years ago." He added: "I enjoyed that time in my life, and that's where I come from - small town life, where everything was centered around church and school. 'Muddy Water' is a prodigal son kind of thing for me."
Trace Adkins' Celebrity Apprentice co-star, the actor Stephen Baldwin, stars in the song 's music video. Adkins explained to CMT News why he chose Baldwin, who converted to evangelical Christianity shortly after the 9/11 attacks, for the promo: "When I recorded this song, I thought about Stephen. I thought if this was ever a single, which I didn't think it would be, by the way... we're gonna do a video for this because Stephen would be perfect because this song mirrors his life, too, and the road that his life has taken -- where you went astray and came back. And the work that he does now and his ministry and all that stuff, I knew that he would like this song. So I sent it to him, and it seemed like providence when I said, 'This is the only week I have available to do this video,' and he looked at his calendar and said, 'That's the only week that I could do it.' Yeah, it was meant to be."