In 1916 werd hij in New York lid van het "Society Orchestra" van James Reese Europe. Hij haalde Europe over om ook zijn vriend, de pianist en componistEubie Blake aan te nemen. Hij hielp Europe met het oprichten van een militaire band voor een regiment van de New York National Guard, een regiment waarin niet-blanken waren ondergebracht en dat onder de naam New York 369th Infantry Regiment actief was in Frankrijk tijdens de Eerste Wereldoorlog. Europe was in die band luitenant en Sissle diens sergeant, en zanger.[3] De band speelde gesyncopeerde muziek en heeft waarschijnlijk de jazz in Frankrijk geïntroduceerd. Na de oorlog was Sissle actief in Europe's burger-versie van deze militaire band en met de groep maakte hij plaatopnames voor Pathé, waarop hij zong.[4]
Na de moord op James Europe, in mei 1919, nam hij met hulp van Eubie Blake tijdelijk de leiding van de band op zich. Het was in die tijd een van de eerste bands die muziek maakte die in de buurt van jazz kwam. Met Blake, die hij al in 1915 had leren kennen, vormde hij tevens een vaudeville-duo onder de naam "The Dixie Duo". Voor Blake's ragtime-songs schreef Sissle de liedjesteksten en veel van die liedjes vormden uiteindelijk de basis van de musicalShuffle Along, die in 1921 zijn première beleefde op Broadway. Deze musical liep ruim 500 voorstellingen en katapulteerde de carrière van Josephine Baker, Adelaide Hall en Paul Robeson. De hit "I'm Just Wild About Harry" diende later, in 1948, met aangepaste tekst, als campagnesong voor Harry S. Truman. Een andere hit uit de musical was "Love Will Find a Way".[5][6]
In 1922 had het tweetal succes met "Arkansas Blues (A Down Home Chant)", dat de tiende plaats in de hitparade haalde. Een jaar later traden de twee op in een paar korte films van Lee DeForest, waaronder Sissle and Blake Sing Snappy Songs met (fragmenten van) de nummers "Sons of Old Black Joe" en "My Swanee Home". Deze films behoren tot de eerste films waarin Afro-Amerikaanse muzikanten in een geluidsfilm te zien en horen waren.[7]