Пирлапон је византијски назив за утврду од кога је настао данашњи назив града Прилеп (Прилепски град).
Марков град је назив везан за најпознатијег владара града краља Марка Мрњавчевића знаног као Краљевић Марко.
Маркове куле је назив који је тврђава добила по остацима кула подигнутих на великим каменим формацијама које се називају исто тако.
Положај тврђаве
Тврђава је смештена на стеновитом врху који се диже над Прилепом прекривеном великим каменим формацијама које су због своје спектакуларности проглашене за природно добро Северне Македоније. Ове формације су искоришћене као основа за градњу кула и бедема. Сам врх поседује четири засебна велика камена узвишења на којима је подигнута тврђава са цитаделом смештеном на највишем од њих (северозападном). Целокупан простор који је некада обухватала тврђава налази се северозападно од данашњег града.
Град се после тога налазио у саставу Византије, Бугарске и Епирске деспотовине, а крајем 13. века га осваја краљ Милутин (1282–1321). Душан Силни га назива великославним градом и у њему смешта један својих „дворова царских”. Он га 1350. године предаје на управу свом жупану Вукашину Мрњавчевићу (1366–1371), који је 1366. године проглашен за краља. После пропасти браће Мрњавчевић на Марици 1371. године Прилепски град постаје престоница Вукашиновог сина Марка који је као османлијскивазал са титулом краља управљао околином све до своје погибије у бици на Ровинама 1395. године. После његове смрти Османлије анектирају целокупну његову област и преузимају контролу над Прилепом. У самом граду нису дуго задржали своју посаду и он је наскоро био напуштен и препуштен пропадању.