Celestin hatte kreolische Ursprünge und arbeitete in seiner Jugend auf Plantagen und als Koch bei der Eisenbahn, bevor er sich teilweise autodidaktisch Gitarre, Posaune und Trompete (Kornett) beibrachte. Das Kornett wurde sein Hauptinstrument. Er spielte in kleineren Städten, bevor er 1906 nach New Orleans zog. Er spielte zunächst in den Brass Bands (Street Bands) „Imperial“, „Olympia“, der „Henry Allen Brass Band“ und der „Excelsior Brass Band“ (ab 1908) und in der Tanzband von Jack Carey, bevor er 1910 die Chance bekam, Leiter der Tanzband in der „Tuxedo Dance Hall“ in Storyville zu werden. Auch nachdem die Tanzhalle 1913 wegen einer Schießerei geschlossen wurde, behielt er den Namen bei, untermauert dadurch, dass er die Musiker in Smokings („Tuxedos“) kleidete. Die sehr populäre Band wurde zeitweise mitgeleitet vom Posaunisten William Ridgely, bevor beide sich im Streit trennten und konkurrierende „Tuxedo Bands“ gründeten. Sie machten 1925 Aufnahmen für Okeh und unter Celestin als „Original Tuxedo Jazz Orchestra“ in den 1920er Jahren bei Columbia. Bis Anfang der 1930er Jahre tourte die Band entlang der Golfküste. In der Band spielten u. a. Peter Bocage, Louis Armstrong und Lorenzo Tio. Daneben leitete Celestin die „Tuxedo Brass Band“, in der u. a. Louis Armstrong und King Oliver spielten. Während der Depression musste er die Band auflösen. Während des Zweiten Weltkriegs arbeitete er auf einer Schiffswerft, leitete danach aber wieder eine Band, die regelmäßig im „Paddock“ in der Bourbon Street spielte, wo sie auch häufig über Radio übertragen wurden und deren Live-Spiel eine Touristenattraktion war. Nach Celestins Tod wurde die Band vom Posaunisten Eddie Pierson und ab 1958 vom Banjospieler der Band Papa French übernommen und danach von seinem Sohn Bob French.
