Se pare că cetele tătare care au distrus în același an cetatea Rodna, au trecut munții prin pasul Cârlibaba în martie 1241. Este probabil că voievodul maramureșean Bogdan I a trecut în 1359-1360 prin teritoriul actualei comune Cârlibaba în momentul descălecării/întemeierii Moldovei. Pe stânca din centrul comunei se află un monument comemorativ care amintește de trecerea lui Bogdan I.
Ca reper toponimic al braniștei mănăstirii Putna, "vârful Cârlibahului" este menționat pentru prima dată în hotarnica moșiei mănăstirești din 9 august 1551, deci în timpul domniei lui Ștefan Rareș, același toponim, "gura Cârlibahului", fiind folosit și în hotarnica din 10 aprilie 1645. O altă atestare o aflăm din scrisoarea pârcălabului Sucevei, Mihaly Tolnay, datată din 1595 și în baza căreia Nicolae Iorga a transcris "hidronimul Cârlibaba" sub forma de Cramabahalu. În ceea ce privește toponimele localităților de pe teritoriul comunei, acestea sunt menționate pentru prima dată în uricul din 15 februarie 1410, când Alexandru cel Bun a donat muntele Suhard mănăstirii Moldovița.
Prima mențiune despre existența comunei se datorează călugărilor de la mănăstirea Putna care în 1629 scriau că atunci când Miron Barnovschi Movilă a trebuit să plece pentru a ocupa tronul Moldovei, "a găsit țara ca fără domn, prădată de tătari și tâlhari, care au lăsat Sucevița numai cu piatră, iar alții sunt la Cârlibaba și mănăstirea stă în frică mare". Întemeierea vetrei satului Cârlibaba s-a făcut după data de 20 mai 1762, când egumenul mănăstirii Putna, Vartolomei Măzăreanu, colonizează braniștile mănăstirești cu "niște ruși din Putila", deci cu câteva familii de huțuli, dar recensămintele din 1774 și 1775 nu menționează existența Cârlibabei. În timp, granița dintre Transilvania și Principatul Moldovei a rămas fixată pe cursul superior al Bistriței Aurii.