Powstanie portolanów było ściśle związane z upowszechnieniem się kompasu (wprowadzonego ok. XI w.). Świadczy o tym ich forma (północna orientacja, róże wiatrów) i sposób, w jaki z nich korzystano. Pierwsze znane portolany pochodzą z końca XIII w. Są jednak na tyle liczne i szczegółowe, że powszechnie uznaje się, że poprzedzała je dłuższa tradycja kartograficzna. Najstarszy zachowany portolan to Carta Pisana z ok. 1275.
Portolany powstały w morskich republikach Genui i Wenecji. Później centra kartograficzne powstały również w Barcelonie i na Majorce, a także w miastach Maghrebu i Imperium Osmańskiego. Początkowo prawdopodobnie były dodatkami do periplusów opisujących podróże morskie. Następnie rozwinęły się do postaci samodzielnych map. W XIV i XV w. pojawiły się atlasy zawierające wiele portolanów, a czasami mapę świata.
Początkowo opisywały jedynie basen Morza Śródziemnego, następnie morza wschodnie (Morze Czarne i Czerwone), Afrykę Wschodnią i północne wybrzeża Europy (wraz z Wyspami Brytyjskimi i Skandynawią).
thumb|Figura Krzysztofa Kolumba korzystającego z portolanu. Muelle de las Carabelas w Palos de la Frontera.