Kentin ilk olarak İ.Ö. 2. binde Palaimindos adı ile Lelegler tarafından kurulduğu tahmin edilmektedir. Strabon’un rivayet ettiğine göre Myndos, Bodrum Yarımadası üzerinde kurulan 8 Leleg kentinden birisidir. Diğer Leleg kentleri: Termera, Side, Madnasa, Padasa, Uranium, Telmessos ve Theangela/ Syangela’dır. Yine Strabon’a göre, Karia Satrabı Mausolos İ.Ö. 4. yüzyılın ortalarına doğru sekiz kentten altısını boşaltarak, buralarda yaşayan insanları zorla Halikarnassos’a yaşamaya mecbur bırakmıştır. Bu zorunlu göç esnasında Myndos’a dokunulmamış, hatta, kent Mausolos’un parasal yardımı ile o dönemin modern şehircilik anlayışına göre yeniden inşa edilerek, etrafı sur duvarı ile çevrilmiştir. Palaimindos olarak adlandırılan eski kentin Kocadağ olarak adlandırılan Yarımada üzerinde kurulu olduğu tahmin edilmektedir. Günümüze kadar ulaşan kentin büyük bir bölümü Mausolos tarafından kurulan yeni kente aittir. Bununla birlikte Roma İmparatorluk çağında da büyük eklemelerin söz konusu olduğu tahmin edilmektedir.