Primele menţiuni documentare ale Orheiului datează din ultima treime a secolului al XV-lea şi se referă la pîrcălabii cetăţii Orhei, situată la 18 km mai jos pe cursul Răutului de locația actuală a orașului Orhei. Vechiul oraș părăsit în primele decenii ale secolului al XVI-lea este cunoscut astăzi sub denumirea Orheiul Vechi, iar noua așezare apărută pe la mijlocul secolului al XVI-lea, a fost numită Orhei. Așezarea veche a devenit un sat obișniut care a dispărut la începutul secolului al XVIII-lea.

Arheologii au descoperit la Orheiul Vechi o veche cetate din lemn și pămînt din secolele XII-XIII, care a fost distrusă în urma invaziei tătaro-mongole din anii 1241-1242. În aceeași vatră în jurul anului 1330 tătaro-mongolii au construit fortificații și chiar un oraș de tip oriental, numit Șehr-al-Gedid (în traducere Orașul Nou). În anul 1369 tătaro-mongolii sînt izgoniți din regiunea pruto-nistreană, iar populația băștinașă se așează cu traiul în vatra orașului, numit de către autohtoni Orhei. Extinderea teritorială a Țării Moldovei prin includerea spațiului șintre Nistru și Prut a favorizat dezvoltarea Orheiului, care devine un centru al producției meșteșugărești și schimbului de mărfuri. Stabilitatea politică în timpul domniei lui Alexandru cel Bun (1400 – 1432) a contribuit la transformarea localității în tîrg. Mărturie sînt numeroasele monede emise în domnia lui Alexandru cel Bun, dar și cele străine descoperite de arheologi la Orheiul Vechi.

T. Nesterov ca urmare a investigațiilor a ajuns la concluzia că cetatea de piatră de la Orheiul Vechi are caracter oriental, diferit de cetățile medievale moldovenești din secolele XIV-XV, fapt ce i-a permis autorului să presupună că complexul dat ar fi mai vechi decît se credea anterior.

Cetatea de piatră înălțată de tătaro-mongoli, deși era deteriorată a servit moldovenilor drept centru de apărare. În domnia lui Ștefan cel Mare (1457-1504) citadela este reconstruită și transformată în reședință a pîrcălabilor de Orhei. La 1 aprilie 1470 în documente este menționat un pîrcălab al cetății Orhei, care îndeplinea și funcții administrative în ținut. Construind o cetate de pămînt și lemn la Orhei Ștefan cel Mare urmărea să consolideze sistemul defensiv al Moldovei, să o apere de incursiunile tătarilor. Dovadă a importanței pe care o acorda Ștefan cel Mare Orheiului, servește faptul că dregătoria de pîrcălabi de Orhei era ocupată de boierii devotați voievodului, ca Radul Gangur, Galeș, Vlaicu, Grozea Micotici, Ivanco și Alexa.

Pe parcursul secolelor XV-XVI, interiorul fortificației a adăpostit, concomitent cu palatul pîrcălabului și locuințele unor orășeni. Citadela de piatră constituia, centrul principal de rezistenţă în sistemul de apărare al Orheiului, cuprinzînd la temelie un dreptunghi de circa zece mii metri pătraţi. Pereţii citadelei erau zidiţi din blocuri de piatră, întărite cu mortar de var. La colţuri citadela era străjuită de turnuri cilindrice. Turnuri semicilindrice au fost înălţate lîngă pereţii dinspre apus, sud şi răsărit. Peretele nordic – din partea malului abrupt al Răutului era sprijinit de două întărituri masive de piatră – contraforturi. Intrarea în citadelă era dinspre sud. Deasupra ei se înălţa un turn, ambele părţi ale porţii erau străjuite de doi piloni.

În anul 1499 ca urmare a unei incursiuni a tătarilor tîrgul și cetatea Orhei au fost devastate. Deși citadela a rămas îm nîinile moldovenilor, capacitatea ei de apărare nu a fost pe deplin refăcută. În 1513 o nouă invazie a tătarilor a afectat serios cetatea. Incursiuni ale tătarilor au avut loc și în anii următori, prejudiciind grav cetatea, tîrgul și întreg ținutul Orhei. Campania sultanului turc Soliman Magnificul în vara anului 1538 a avut urmări dezastruoase pentru cetatea și ținutul Orheiului, dar și mai grav era pericolul transformării Orheiului în cetate turco-tătară în vederea consolidării otomanilor în spațiul dintre Prut și Nistru.

Potrivit documentelor medievale, pe vremea celei de-a doua domnii a lui Petru Rareş, adică după 1541, pe locul vechii cetăţi a Orheiului a fost înălţată o nouă cetate de piatră, care ulterior a fost folosită de unii domni moldoveni în vederea restabilirii capacităţii de apărare a Ţării Moldovei. Cetatea din piatră este distrusă, probabil din porunca lui Alexandru Lăpușneanu, care la cererea turcilor a desființat mai multe cetăți. În jurul anului 1600, domnitorul Ieremia Movilă a încercat să reconstruiască cetatea, dar fără succes.