Bu bölgede yapısal izler bırakan ilk yerleşim yeri; Aziz Peter (St. Peter) kalesinin bulunduğu şimdiki küçük kayalık İadaydı. (O zamanlar kale tamamen suyla çevriliydi). St. John şövalyeleri kendi kalelerini inşa etmeye geldiklerinde, M.Ö. 1100'lerde Dorlar tarafından yapılmış daha eski bir kalenin kalıntılarıyla karşılaşmışlardı.

M.Ö. 5'ci yüzyılda yaşamış olan ve "Tarihin Babası" olarak tanınan Herodot, Halikarnas'ta doğmuştur. Herodot, Dorlar'ın, Peleponez'in doğu kıyılarında Trözen'den geldiğini yazmıştır. Dorlar, yeni adalarına Zefiriya, yerleştikleri bölgeye de Zefiriyum adını verdiler.

Tarihçiler, Harikarnas'ın temellerinin nereye dayandığı hakkında çok az bilgiye sahiptirler. Halikarnas hakkındaki ilk bilgiler M.Ö. 7.y.y.'a dayanır. Halikarnas, Heksapolis-Dor Konfederasyonu'na bağlı altı üyeden biriydi. Ayrıca karada Knidos şehri, Kos adası ve Rodos üzerindeki üç şehir de bu üyeler arasındaydı.

Bu şehirleri kurmak, oraya sonradan gelerek çevreyi önceki sakinleriyle paylaşmak zorunda kalan Dorlar için hiç de kolay değildi. Karyalılar olarak bilinen bölge yerlilerinin yoğun ve şiddetli saldırılarından kendilerini korumak zorundaydılar. Homeros "İliyada"sında Karyalılar'dan "dil barbarları" diye söz etmiştir. (Bununla birlikte, bir çok dilbilimci, Bodrum'un da içinde bulunduğu bölgedeki lehçenin Türkiye'nin batısındaki en kaba lehçe olduğunu belirtmiştir). Eski tarihçiler, Karyalıların Yunanlılar'a miğferlerinin üzerindeki sorgucu nasıl takacaklarını ve önceleri omuz hizasına savrularak kullanılmakta olan kalkan kabzasını nasıl kullanacaklarını öğrettiklerini yazmışlardır.

Bir Yunanlı'nın Salmakis'te han açmasıyla (bu han günümüzde, Bodrum limanının batısında, şimdiki Bardakçı Koyu'nun suları altında kalmıştır) Dorlar ve Karyalılar bölgeyi birlikte yönetir duruma gelmişlerdi; hatta Karyalılar zamanla kolonidekilere oranla daha düzenli bir yaşantı kurdular. Her iki ırk da barış içerisinde yaşamağa başladı ve karşılıklı ticari ilişkilere de girişildi.

Salmakis pınarının bir çok rahatlatıcı özellikleri olduğu rivayet edilmiştir. Bir başka rivayet de, içimi mükemmel olan bu suyun erkekleri yumuşattığı, efemineleştirdiği, hatta bazı durumlarda iktidarsızlaştırdığı hakkındadır. Bu iddialar sonucunda da Hermafrodit efsanesi doğmuştur.

Rivayete göre, güzellik Tanrıçası Afrodit'in delikanlılık çağındaki oğlu bir gün çeşmeden akan suyun oluşturduğu bir gölde yüzer. Gölün perisi Salmakis, ona aşık olur ve tanrılara tek bir vücutta yaşayabilmeleri için yalvarır. Dileği kabul edilir; tanrılar da yarı erkek, yarı kadından oluşan Hermafrodit'i yaratırlar.

Herodot, Halikarnas'ın çevresinde İyonyalı denilen bir grup yerli halkın giderek çoğaldığını, hatta iki halkın içiçe yaşadıklarını yazmıştır. Bu durum Heksapolis'in diğer sakinlerinin pek hoşuna gitmemiş ve bir Halikarnaslı'nın yanlış bir davranışı, Halikarnas'ın ittifaktan kovulmasına zemin hazırlamıştır.

Apollo'nun onuruna her yıl düzenlenen Tropium'daki oyunlara altı şehir de katılır. Bir yıl, Agasides adındaki bir Halikarnaslı bronz madalyayı kazandığında, törelere uyup, ödülü Apollo'ya adamak yerine, evindeki duvara asınca, diğer Dor şehirlerini öfkelendirmiş ve Halikarnas'la ilişkilerini kesmeleri için onlara yeterli nedeni sağlamış oldu.

M.Ö. 5'ci y.y.'da Halikarnas tamamiyle bir İyon şehri görünümündeydi. Herodot ve amcası Panyasis o sıralarda eserlerini İyonca'da yazmışlar, bu döneme ait hiç bir eserde de Dor lehçesinin izine rastlanmamıştır.

M.Ö. 546'da Persler (İranlılar) kıyıdaki Yunan şehirlerini işgal etmişler, Halikarnas da diğer şehirlerle birlikte düşmüştür. Pers yönetiminde birçok hanedan, şehri yönetimiştir. Bunların en ünlüsü de M.Ö. 480'de yönetime geçen I.Artemis'tir.

Herodot yazılarında, bu dikkat çekici kadına geniş yer vermiştir; o sıralarda Yunanistan'I istila etmekte olen Zerzes'in donanmasına I. Artemis'in gereksizce gönüllü asker toplanması hakkında şöyle yazar: "…erkekçe tavır ve davranışları onu savaşa sürükledi… Yunanistan'a yapılan saldırıya, kadınlığını gözardı ederek katılması, beni gerçekten de etkilemiştir…". Bu saldırıda bir savaş gemisini büyük bir başarıyla kumanda etmesi, Zerzes'e "Emrindeki erkekler kadın, kadınlarsa erkekçe davrandılar" dedirtmiştir.

Artemis'in oğlu Pisindalis, onun ardından başa gelmiş ve Halikarnas'ın (Kos ve başka şehirler de olmak üzere) yönetimini sürdürmüştür. Tarihçiler Pisindalis dönemi hakkında pek yorum yapmazken, oğlu II. Lidamis için acımasız, zalim ve baskıcı sıfatlarını kullanmaktan kaçınmamışlardır. Herodot, II. Lidanis'in otoritesi ve zulmü karşısında dayanamayarak anayurdunu bırakıp, Samos adasına gitmiştir. 1856'da arkeolog Sir Charles Newton,

II. Lidanis'in kendi politikasına uymayan görüşlere karşı olduğu olumsuz tavrı açıkça ortaya koyan bir kanun belgesi bulmuştur. II. Lidanis'in ardından kimin yönetime geldiği, ya da zulmünün neden ve nasıl sona erdiği hakkında hiç bir bilgiye sahip olmamakla beraber, bölgede M.Ö. 4 ci y.y.'da büyük bir değişimin yaşandığını söyleyebiliriz.

Bir önceki yüzyılda, Pers yönetimi bölgeden atıldıktan kısa bir süre sonra, Atina ile Persler arasında imzalanan "Kral Barışı" antlaşmasıyla, Asya'daki şehirlerin yönetimi tekrar Perslerin idaresine geçmiştir. Persler bölgeyi küçük prensliklere bölmüş ve M.Ö. 377'lerde Kral Mozulus, Karya ve Halikarnas valisi olarak bölgeyi yönetmiştir.

Mozolus'un iktidarına kadar Halikarnas oldukça küçük bir şehir niteliğindeydi, ancak Mozolus'un bu bölge için müthiş projeleri vardı. Ayrıca, bu bölgenin istihkam ve ticaret için çok elverişli olduğunun da farkındaydı. Başkent, Milasa'dan (bugünkü Milas) buraya taşıyarak şehrin etrafına büyük ve uzun duvarlar inşa ettirmişti; bu duvarların günümüze kadar ulaşan bölümleri halen Bodrum'dadır. Bölge nüfusunu arttırmak amacıyla Mozolus, diğer altı şehrin yerleşim yerlerini de buraya taşıttı. Mozolus, bu projelerini uygulayabilmek için, idaresinde halkı ağır vergilere boğdu. Öyle ki; "omzu aşan uzunluktaki saçtan bile vergi alacak kadar…".

Mozolus'un projelerinden biri de, klasik çağdaki Bodrum'dan günümüze ulaşabilen tek yapı olan Antik Tiyatro'dur. Bodrum'un ortasındaki Göktepe dağının güney eteklerindeki bu tiyatro, Anadolu'nun en eski tiyatrolarından biridir. 1960'larda bir grup Türk tarafından restore edilen bu tiyatro, günümüzde de Bodrum'daki bir çok festivale sahne olmaktadır.