"Eh Hee" was written as an evocation of the music and culture of the San people of southern Africa. In a story told to the Radio City audience (an edited version of which appears on the DVD version of Live at Radio City), Matthews recalls hearing the music of the Khoisan and, upon asking his guide what the words to their songs were, being told that "there are no words to these songs, because these songs, we've been singing since before people had words". He goes on to describe the song as his "homage to meeting... the most advanced people on the planet".
The song debuted in February 2006 on the Dave Matthews & Friends Caribbean cruise under the title "Ayhee". It was performed as part of a mini-performance on each individual ship after stormy conditions cut the main show short. Other than a solo performance by Matthews in Manchester a few months later, it was not performed again in full until 2007 at an acoustic concert at Radio City Music Hall by Matthews and Tim Reynolds. Beginning with that concert, the title was changed from "Ayhee" to "Eh Hee" on the setlist, and its performance was later released as part of the Live at Radio City album.
The next performance of the song was performed by the entire Dave Matthews Band in August 2007 in Noblesville, Indiana and became only the second to ever be performed by the band, as well as Matthews and Reynolds, Dave Matthews & Friends, and as a solo by Matthews. "Eh Hee" went on to become one of the most performed songs by the band during the summer 2007 tour, and a live performances of the song were released on the albums Live at Piedmont Park and 2008's Live at Mile High Music Festival.