Будівництво замку почалося в 1402 році столітті на місці колишньої сельджукської фортеці під керівництвом лицарів ордена Св. Іоанна Єрусалимського, які прибули з грецького острова Родос і окупували територію сучасного Бодрума.

Будівництво фортеці велося під керівництвом німецького архітектора Генріха Шлегенхольта, а як матеріал для будівництва використовувалися блоки із зелених вулканічних каменів, а також мармурові колони і каміння з розташованих практично навпроти руїн одного з семи чудес стародавнього світу — Гробниці Мавзола.

Отримана фортеця в той час стала одним з найкращих зразків фортифікаційних споруд і мала все необхідне для запобігання нападам, як з моря, так і з суші: добре укріплений Північний рів, кілька оглядових веж, 7 воріт і тунель, а також головний вхід, який був повністю захищений. У каменях були зроблені спеціальні дірки, через які на нападників виливали гарячу олію, а зубчасті стіни захищали фортецю в разі штурму. Основною загрозою в той час були турки-османи, тому замок був завжди готовий до оборони і ретельно охоронявся.

Внутрішня територія замку була поділена за мовною ознакою на зони, що охороняються тією чи іншою групою лицарів. Згодом кожна з веж замку стала носити назву в честь країни, яка займалася фінансуванням будівництва. Це — Англійська, Німецька, Французька, Італійська та Іспанська вежі, кожна з яких має свої відмінні архітектурні особливості та історію.

У замку також розташована вежа під назвою Лиман або Портова вежа, яка сьогодні є головним входом в замок. Існує також потайний тунель, побудований з метою екстреної евакуації, що з'єднує Замок і древній амфітеатр Бодрума.

В епоху свого розквіту У фортеці постійно проживало близько 50 лицарів різних національностей і рядові солдати, основним завданням яких була оборона замку і його околиць.

В 1522 році султан Сулейман Пишний напав на резиденцію лицарів ордена Св. Іоанна на острові Родос, і після тримісячної атаки ті були змушені здатися. За укладеним договором лицарі повинні були покинути острів Родос, а також ще 5 завойованих ними островів у Середземному морі, серед яких виявився також і стародавній Галікарнас - фортеця Св. Петра. 1523 року лицарі повністю покинули острова і осіли на Мальті, а Бодрумська фортеця дісталася туркам, які прибудували до неї мінарет і турецьку лазню.

Пізніше в 18 столітті замок використовувався як військовий гарнізон, коли греки оголосили незалежність островів, а також як в'язниця вже в 19 столітті.

Під час Першої світової війни французький військовий корабель розбомбив частину фронтальної стіни замку і кілька веж, а також зруйнував мінарет мечеті після того, як кораблю було відмовлено в швартуванні в місті. В кінці першої світової війни Бодрум окупували італійці, котрі завоювали також частину узбережжя від Кушадаси до Анталії. Вони відновили Французьку і Італійську вежі, але в цей час почалася війна за Незалежність Туреччини, очолювана Мустафою Кемалем Ататюрком. У 1921 році італійці були змушені залишити фортецю, яка перейшла у володіння зароджується Турецької республіки.

Протягом перших 10 років після заснування Республіки замок був повністю покинутий. На його території було побудовано кілька житлових будинків, відновлено мечеть і купальню. Однак в цілому з огляду на напівзруйнований стан - німих останків колишньої могутності - це місце популярністю не користувалося, більш того, багато місцевих жителів намагалися уникати його.

До 1950 року напівзруйнована фортеця використовувалася як корабельна верф і «кладовище» зазнавших корабельної аварії і не придатних до плавання кораблів.

Ідея перетворення напівзруйнованого замку в музей належала англійському журналістові Петеру Трокмортону, який займався вивченням цих місць і в один прекрасний момент знайшов під водою залишки добре збережееого стародавнього корабля. Разом з однодумцями, серед яких були Джордж Басс, Гонор Фрост, Мустафа Капкін, а також директор Ізмірського археологічного музею Хакке Гюльтекін, директор Бодрумської школи Халук Ельбі і академік Азра Ерхат, Петер звернувся до Турецького уряду з пропозицією про реконструкцію фортеці і організації тут музею.

Результатом вжитих зусиль стало початок реконструкційних робіт у фортеці, що фінансуються державою, а також пізніше — офіційне проголошення замку музеєм в 1961 році.

Першим директором Бодрумського замку став Халук Ельбі, який продовжив активні роботи по відновленню стін і веж замку, по озелененню території фортеці, а також відкрив перші виставкові експозиції в Залі готичних лицарів і Капелі.

У 1962 році в приміщеннях колишнього замку був створений Музей підводної археології, в якому виставлено улубурунський скарб.