The Civil War reference above is probably correct. The song appeared in 1862.

New York Herald (Oct. 11, 1862):

"CAPTAIN JINKS OF THE 'HORSE MARINES,' New song, with colored lithograph, 40c....'Paradise Alley,' 25c...F. BLUME, music store, 206 Bowery."