Musically, "Bye and Bye" is what Oliver Trager calls an "easygoing, lilting ballad...something one would expect from Leon Redbone or, from an earlier era, Bing Crosby. Some Dylanists have traced the musical source for 'Bye and Bye' to 'Having Myself a Time,' a song popularized by Billie Holiday and written by Leo Robin and Ralph Rainger".
Lyrically, however, "Bye and Bye" appears to have darker concerns. According to Trager again:
["Bye and Bye"] slowly gives way to the sentiments of a scary stalker. As Richard Harrington wrote in his September 16, 2001, Washington Post review of Love and Theft:
In "Bye and Bye," Dylan sings "The future for me is already past / You were my first love, you will be my last." Take him literally and it's about obsessional desire for a particular woman. But it's also about American roots music and Dylan's abiding appreciation for it, and inspiration from it, over the course of half a century.
Dylan first performed the song live in October 2002.