Bukti arkeologi mencadangkan bahawa tinggalan-tinggalan terawal Persepolis wujud sejak dari sekitar 518 SM.

Andre Godard, ahli arkeologi Perancis, yang mengekskavasi Persepolis pada awal dekad 1950-an mempercayai bahawa Cyrus Agung ialah yang memilih tapak ini untuk Persepolis, manakala teres dan istana-istana yang besar di bina oleh Darius Agung.

Darius menitahkan pembinaan Istana Apadana dan Balai Perdebatan (Tripylon atau Balai Tiga Pintu), serta Bangunan Perbendarahaan Empayar dan persekitarannya, yang disiapkan pada zaman pemerintahan puteranya, Raja Xerxes I. Pembinaan bangunan-bangunan tambahan di teres tersebut berterusan sehingga kejatuhan dinasti Achaemenes.