Istnieje przypuszczenie, że w okolicy dzisiejszego miasta istniała niewielka forteca już w IX stuleciu.
Prawdopodobne pod koniec XV wieku w granicach obecnego miasta wzniesione zostały niewielkie umocnienia, które miały chronić ziemie mołdawskie przed najazdami Tatarów.
W Turcji W 1538 roku Turcja wydzieliła z Mołdawii jej południową część (Budziak) i przyłączyła do ejaletu Silistry. W mieście, któremu Osmanowie nadali nazwę Bendery (z perskiego – przystań, miasto portowe), postanowiono wznieść nową, murowaną fortecę, z uwagi na strategiczne położenie ośrodka na wysokim brzegu Dniestru. Zaprojektowany przez Sinana i zbudowany według wzorców zachodnich zamek powstał w trzy lata, do 1541 roku.
thumb|left|200px|Karol XII w Benderach W końcu XVI wieku twierdza była kilkakrotnie oblegana przez oddziały mołdawskie, m.in. w 1574 roku przez armię Jana Srogiego, za każdym razem bez powodzenia. Następnie fortecę atakowali również Kozacy zaporoscy. Przy atakach na fortecę niszczona była, przy ataku Kozaków doszczętnie, funkcjonująca przy niej osada. W związku z powtarzającymi się atakami na twierdzę w 1619 roku Turcy dokonali jej całkowitej przebudowy. Kamienne baszty i mury, niezdolne już do stawienia oporu nowoczesnej artylerii, zastąpiono umocnieniami typu bastionowego.