Po nepříliš úspěšném turné po Americe se Marius dostal do Paříže, kde se objevil na jevišti Comédie Française po boku jedné z nejslavnějších romantických tanečnic, Italky Carlotty Grisi, pozdější první představitelky hlavní role baletu Giselle (kde jí byl partnerem Mariův bratr Lucien). V Paříži nicméně nezůstal, odjel do Bordeaux, kde se stal prvním sólistou v tamním Grand Théâtre a opět se shledal se svým učitelem Vestrisem. Vedle hlavních mužských rolí v baletech jako La Fille mal gardée, Giselle či La Péri dál rozvíjel své choreografické schopnosti. V této době vznikly jeho první samostatné balety: La Jolie Bordelaise (1840), L’Intrigue Amoureuse (1841), Les Vendanges (1842) a Le Langage des Fleurs (1844).
Z Bordeaux až do Petrohradu
Po Bordeaux následoval kontrakt v Madridu (1844–1847), odkud musel Petipa odejít poněkud narychlo. Provalila se totiž jeho avantýra s místní vdanou šlechtičnou, jejíž manžel vyhrožoval tanečníkovi soubojem. Jeho další kroky vedly přes krátkou zastávku v Paříži již do ruského Petrohradu, kam byl pozván Alexandrem Gedeonovem, ředitelem Carského divadla. Jedna z teorií nicméně tvrdí, že Gedeonov měl původně zájem o Mariova bratra Luciena. Ten měl ovšem závazky vůči Opeře v Paříži, a tak doporučil na nabízené místo svého bratra. Ať už byly ovšem pohnutky jakékoli, pravdou zůstává, že od roku 1847 působil Petipa v Petrohradu jako tanečník, baletní pedagog a choreograf. Nejdříve coby asistent baletního mistra Julese Perrota (1849–1858), poté současně s dlouholetým rivalem Arthurem Saint-Léonem (1860–1869). V roce 1871 se stal 1. baletním mistrem a současně vůdčí osobností ruského baletu a jeho repertoáru, ve své funkci vydržel až do roku 1901.