The origins of this song are unclear. It apparently evolved in the early 1900s from a number of similarly titled gospel songs, including "When the Saints Are Marching In" (1896) and "When the Saints March In for Crowning" (1908). The first known recorded version was in 1923 by the Paramount Jubilee Singers on Paramount 12073. Although the title given on the label is "When All the Saints Come Marching In", the group sings the modern lyrics beginning with "When the saints go marching in". No author is shown on the label.

Louis Armstrong played this on Ed Sullivan on September 20, 1959.