Mucha se s Gauguinem potkal poprvé v roce 1891 v kavárně Crémerie Madame Charlotte Caronové na Rue de la Grande Chaumière 13, na levém břehu řeky Seiny v Paříži. Tento podnik, situovaný přesně naproti Académie Colarossi, kde oba umělci v minulosti studovali, se stal místem setkávání tehdejších bohémů, kteří měli hluboko do kapsy a mohli se zde najíst na dluh nebo platit svými uměleckými díly.
Mucha vzpomínal: „Přišel si sednout k našemu stolku mezi [Władysława] Ślewińského a mne. Byl to mohutný Bretonec, oblečený v něčem, co se podobalo národnímu kroji. Na hlavě měl kožešinový astrachán a přes ramena široký plášť s ozdobnými sponami. Madame Charlotte ho představila jako námořníka, který také maluje: Monsieur Gauguin. Brzy se z nás stali přátelé [...]. Od té doby Gauguin přicházel denně.“
Později téhož roku se Gauguin vydal na svou první cestu do Polynésie. Zpět do Francie se vrátil o dva roky později s rozsáhlým souborem prací – odhodlaný prorazit. Protože Mucha věděl, že jeho starší kolega na tom není finančně nejlépe, nabídl mu ke sdílení svůj ateliér na Rue de la Grande Chaumière 8 přesně naproti Crémerie. A právě v rohu Muchova ateliéru dokončoval Gauguin poslední detaily své výstavy 46 prací a 11 plastik vytvořených z velké většiny během pobytu na Tahiti, které byly vystaveny v Galerii Durand-Ruel v Paříži v listopadu 1893.
Na fotkách z té doby, které pořídil sám Mucha, je zřejmé pevné přátelské pouto, které umělce spojovalo. Gauguinova mladičká milenka a zároveň jedna z jeho modelek, Annah la Javanaise, ho často doprovázela do Muchova ateliéru a připojovala se k umělcům, kteří se, když nebyli zaměstnaní prací, bavili převlékáním do kostýmů a pózováním před Muchovým fotoaparátem. Kromě humornějších póz, jako je například fotka s názvem Paul Gauguin hrající na harmonium v Muchově ateliéru, Rue de la Grande Chaumière (1893–1894), stál Gauguin Muchovi modelem i při přípravě ilustrací knížky Judith Gautierové Mémoires d'un Éléphant Blanc (Vzpomínky bílého slona, 1893–1894).
Kromě výrazné slabosti pro Madame Charlotte a její kuchyni, japonské tisky a práci Puvise de Chavannese, sdíleli Mucha s Gauguinem řadu dalších „charakterových rysů“. Oba umělci byli nebývale ctižádostiví a lační po úspěchu a záleželo jim na tom, aby dojem, který vzbuzovali ve společnosti, odrážel jejich jedinečnou estetiku. Ateliér tak byl dalším prostředkem jejich vyjádření a sloužil jako nástroj propagace jejich práce. V lednu 1894 se Gauguin přestěhoval do vlastního studia na Rue Vercingétorix 6, jen pár minut pěšky od Rue de la Grande Chaumière. Stejným způsobem, jakým Mucha vytvořil exotický bohémský interiér, přeměnil se Gauguinův prostor v ódu na primitivní život a lidová umění a upevnil jeho pozici odborníka na původní tahitskou kulturu. V rámci svých pravidelných společenských dýchánků v těchto výjimečných prostorách, kde často nechyběl ani hostitel oděný do excentrického lidového roucha (a v Gauguinově případě navíc s exotickou milenkou po boku), se oba umělci snažili svá díla probudit k životu a upoutat pozornost návštěvníků jedinečným estetickým zážitkem.
V roce 1895 se Gauguinovi podařilo získat prostředky na návrat do Polynésie, kde zůstal až do své smrti v roce 1903. Když Paříž opouštěl, Mucha byl zrovna nemocný a svého přítele už nikdy neviděl.