"Paint Me a Birmingham" is a song written by Buck Moore and Gary Duffy. It was concurrently released by American country music artists Ken Mellons and Tracy Lawrence, whose versions entered the country charts within one week of each other. Lawrence's was the more successful of the two, reaching #4 in early 2004 and becoming his first Top 5 country hit since "Lessons Learned" in 1999.
The narrator describes an encounter on the beach with an artist who is painting ocean scenes. The singer then asks the painter to paint a picture of the plans the man and his lost lover had actually made. The song is in the key of F-sharp major with a vocal range from G♯3 to C♯5.