At first, the band was known as the Friar's Society Orchestra after obtaining a gig at Friar's Inn, but changed their name to the New Orleans Rhythm Kings after their residency ended. Mares is credited with co-writing several of their best known songs including "Tin Roof Blues" in 1923. He also co-wrote the music to "Make Love to Me" for the group and which was a million-seller when revived by Jo Stafford in 1954. The band also recorded with pianist Jelly Roll Morton on piano thus becoming the first multi-racial jazz band to record.
Stitzel co-wrote "Doodle Doo Doo" with Art Kassel in 1924. He co-wrote "Bittersweet" with Ben Pollack. He also wrote the music for "The Chant" in 1926 after the Rhythm Kings broke up in 1925.