Na miejsce budowy wybrano znajdujące się nieopodal Lhasy, wysokie na ok. 300 m wzgórze Marpori („Czerwone Wzgórze”). Na jego zboczach znajdowały się ruiny twierdzy wzniesionej 1000 lat wcześniej przez pierwszego władcę państwa tybetańskiego, króla Songcen Gampo, dlatego miało ono w świadomości Tybetańczyków znaczenie niezwykle istotne.
Nazwa kompleksu nawiązywała do góry Potalaka mitycznej, indyjskiej siedziby bodhisttawy Awalokiteśwary (tyb. Czenreziga), który zgodnie z buddyjską doktryną manifestuje się w osobach dalajlamów.
Budowę rozpoczęto w 1645. Do pracy zaangażowano 7 tys. robotników oraz ok. 1000 artystów i pomimo tego, że pierwszy budynek zwany „Białym Pałacem” ukończono dopiero w 1653, V Dalajlama wprowadził się do niego już w 1648. Budowę kontynuowano i w roku 1690 (po śmierci Lobsenga Gjaco) ukończono tzw. „Czerwony Pałac” (spełniający głównie funkcje religijne). Sukcesywnie rozbudowywana Potala stała się na kolejne 300 lat duchowym i administracyjnym centrum Tybetu.