En 1867, Paulus se produit sur la scène du Concert du XIXe siècle, puis à l'Alhambra et à l'Eldorado. Il se forge ensuite une très solide réputation de chanteur en parcourant les grandes salles de province (Marseille, Lyon, Toulouse...). A l'Alcazar d'Eté à Paris, en 1877, il interprète "Les pompiers de Nanterre" (Philibert-Burani/Antonin Louis). A la Scala, il crée "Je me rapapillote" (Laroche-Paulus/Tac Cohen). Parmi son répertoire des années 1880, citons également surtout "En revenant de la revue" (L. Delormel-L. Garnier/L.-C. Desormes, 1886, créée A la Scala), qui reste son plus gros succès. Le 14 juillet 1886, il la chante et modifie le couplet, à la gloire du général Boulanger.  
A partir de 1883, il est une "vedette" à part entière. Il signe pour trois ans au Concert Parisien, contre un important cachet, ce qui ne l'empêche pas de chanter ailleurs. En 1889, il obtient un autre énorme succès avec "Le père la Victoire"