La Young Tuxedo Brass Band fue fundada en 1938 por John Casimir . Su nombre es un guiño a la Tuxedo Brass Band de Papa Celestin , un conjunto de Nueva Orleans en las décadas de 1910 y 1920. El conjunto generalmente tenía entre nueve y once jugadores, con dos trompetas, dos trombones, dos cañas, un sousáfono o tuba, una caja y un bombo. Su primer disco se publicó en 1958 en Atlantic Records y contó con Paul Barbarin en la batería; otro personal incluyó a Andy Anderson y John Brunious en la trompeta, Clement Tervalon, Eddie Pierson y Jim Robinson en el trombón, los reedists Herman Sherman yAndrew Morgan , Wilbert "Bird" Tillman, sousafón y el baterista Emile Knox.
En 1963, Wilbert Tilman, el sousafonista fundador del grupo y primo de Casimir, tomó el control del grupo, pero se retiró ese mismo año debido a problemas de salud; Andrew Morgan asumió el cargo hasta su muerte en 1972. Después de esto, Herman Sherman se convirtió en el líder del grupo hasta su muerte en 1984. Durante el mandato de Sherman, se presentaron en el Smithsonian Folklife Festival de 1976 para celebrar el bicentenario de los Estados Unidos en Washington DC y nuevamente en 1985 cuando el Festival presentó un programa sobre Luisiana. Aparecieron en la Casa Blanca el Día del Padre de 1978 para la celebración del 25 aniversario del Festival de Jazz de Newport .
La banda grabó con el ex Beatle Paul McCartney en Nueva Orleans en 1975. En 1983, grabaron Jazz Continues en 504 Records of England, que fue una secuela de la grabación de Atlantic Jazz Begins . Este contó con Herman Sherman, saxo alto, Joseph Torregano, saxo tenor, Michael White, clarinete, John Simmons, trompeta, Joshua "Jack" Willis, corneta y melófono; Gregory Stafford, clarinete, Lawrence Trotter, caja, Charles Barbarin (sobrino del gran Paul Barbarin) bombo; Walter Payton, sousafón, Lester Caliste y Clement Tervalon, trombones. Herman Sherman y Clement Tervalon estaban en la grabación original de 1958.
La banda ha estado bajo la dirección de Gregg Stafford desde la muerte de Sherman en 1984 y es una de las últimas bandas de metales tradicionales de Nueva Orleans que toca himnos, cantos fúnebres y canciones del repertorio de metales.