Prvé stopy osídlenia pochádzajú z 3. storočia (včasné klasické obdobie), kedy bolo mesto zriadené ako ceremionálne centrum pre veľkňazov (kráľov). Vo včasnom klasickom období nevznikli ani nápisy, ani významnejšie budovy.

Väčšina dnešnej architektúry a ozdôb fasád podchádza až z obdobia medzi 600 a 800, čiže z tzv. stredného klasického obdobia. Dnešná podoba mesta vznikol počas vlády troch najvplyvnejších vládcov (veľkňazov, čiže kráľov a zároveň vládcov) Palenque. Bol to K'inich Hanab Pakal (vládol 615 – 683, roku 675 začal stavbu Chrámu nápisov) a jeho dvaja synovia Kan Balam (684 – 702) a K'an Hoy Kitam (702 – 711). Hanab Kanal a Kan Balam sú zodpovední za krásne stavby mesta. Túto „dynastiu“ prerušil roku 711 Tonina, ktorý zajal K'an Hoy Kitama. V roku 722 po Kr. dynastiu však obnovil K'inich Ahkal Mo'Nab (721 – 736) z vedľajšej línie kmeňa. Tento dal postaviť aj chrám 19.

Koncom klasického obdobia postavili okolo lokality terasovité opevnenia, zrejme aby mesto ochránili pred útočníkmi zo stredného pobrežia Mexického zálivu. Aj budovy prestavali akoby na účely blokády.

Posledný dátum z Palenque je rok 799.

Ruiny Palenque sú známe od 18. storočia, prvé výskumy robil Angličan J. Maudslay, ale až v 40-tych rokoch 20. stroročia sa začali intenzívnejšie vykopávky, ktoré trvajú dodnes. Neustále sa vyskytujú nové objavy, ako napríklad nedávno objavený trón v Chráme 19.