O podobě původních hradeb nemáme moc informací. Pravděpodobně byly dřevěné či hliněné a jich součástmi byly brány nebo vrata. Kamenné hradby budovali až noví majitelé Prostějova – Pernštejnové. 27. února 1495 Vratislav z Pernštejna za přítomnosti městské rady osobně položil kámen k výstavbě hradeb. V Pamětní knize města máme o tom tento záznam: „…pan Vratislav z Pernštejna učinil počátek zdi stavenie okolo města Prostějova, v ten pátek po svatém Matěji v hodinu čtrnáctú, minutu octavo, ANNO DOMINI MCCCCXCV.“

Celý fortifikační systém zahrnoval třináct bašt, čtyři brány (Plumlovská, Olomoucká, Vodní – Brněnská, Kostelecká), dva vodní příkopy a val.

Prvním zásahem do hradeb byla ve 20. letech 16. století stavba zámku. Při ní byla zbourána Kostelecká brána a místo ní zde vznikla fortna (malá branka pro pěší). Zámek byl napojen na hradby a kolem něj byl vybudován vodní příkop. Další výrazné poškození bylo při pobytu švédských vojsk generála Torstenssona v létě roku 1643. Torstensson nařídil pobořit hradby a zapálit zámek. V osmdesátých letech 17. století byly hradby zčásti opraveny, ale na dalším poškození se podepsal velký požár Prostějova 27. dubna 1697.