Există mai multe versiuni cu privire la originea toponimului Orhei. Potrivit lui Iorgu Iordan, numele orașului vine din ungurescul vár + hely (cetate + loc), însemnând „loc al cetății", cu sensul „locul unde era o cetate". Numele se trage de la ostașii secui pe care voievozii Moldovei îi stabiliseră aici în drumul tătarilor, care stăpâniseră cetatea între 1224 și 1359.

Alți cercetători sunt de  părere că toponimul Orhei este de provenienţă turanică, iar „orga” înseamnă reşedinţa hanului.

Inițial  Orheiul a avut  o altă vatră, în prezent cunoscută sub numele de Orheiul Vechi, care în primele decenii ale secolului al XVI-lea a fost părăsită. Orheiul Vechi este situat la 18  km distanță, spre Sud–Est de orașul Orhei, între satele Trebujeni și Butuceni.

În 1223 hoardele tătare trec Nistrul, călăresc în sus pe Răut jefuind satele și dau de această vale prielnică de la cotitura râului. Cotropitorii n-au stat aici mult timp (deceniile 4-6 ale secolului XIV), dar au reușit să imprime localității o înfățișare orientală. Tătarii au înălțat o moschee, un caravan-sarai, mausolee-mazare. Pe această palmă de pământ, pe ruinele orașului de tip oriental, la începutul secolului XIV a apărut Orheiul Vechi, care a întrat în componența statului feudal moldovenesc întemeiat în 1359. Însă, prima atestare documentară a Orheiului Vechi datează din 1470. Astfel, la  1  aprilie  1470 este  menţionat  documentar  numele  primului  pârcălab  de  Orhei,  Radu  Gangur,   în contextul  finalizării  lucrărilor  de  construire  a  cetăţii  Orhei,  edificarea  căreia  a  început  odată  cu  urcarea  lui  Ştefan  cel  Mare  (1457)  pe  tronul  Moldovei. 

În  anul  1499,  în  urma  unei  invazii  a  tătarilor,  atât  târgul,  cât  şi  cetatea  au  fost  arse  şi  distruse. În  anul  1533,  după  două  mari  incursiuni  devastatoare,  târgul  Orheiului  s-a  strămutat  într-un  loc  mai  liniştit  şi  mai  îndepărtat  de  căile  de  comerţ  şi  de  atacurile  tătarilor.

Prima mărturie documentare referitoare la Orhei pe locul actual datează din 1554 din perioada domniei lui Alexandru Lăpuşneanu, când s-a lucrat la digul de la confluenţa râurilor Cula și Răut, atunci formându-se lacul din faţa localităţii.

Din 1599 Orheiul este trecut în documentele oficiale ca târg, localitatea se dezvoltă devenind un centru al comerțului în regiune, iar unul din proprietarii dughenelor noi apărute este pârcălabul de atunci al Orheiului, Nicoară Donici.

Târgul cunoaşte o deosebită înflorire economică în timpul domniei lui Vasile Lupu (1634-1653), care a refăcut lacul Orheiului, a construit poduri, a reamenajat mai multe străzi, a întemeiat lângă Orhei, o „slobozie”, venitul căreia revenea doamnei sale. Vasile Lupu a fost ctitorul catedralei „Sf. Dumitru”. Paul de Alep, care a trecut prin târgul Orhei în 1653 scria în jurnalul de călătorie: „casele sunt din piatră şi lemn, iar străzile pavate cu scânduri, cum erau şi la Iaşi”.

La 1835 Orheiul a devenit centru de uezd.  A crescut numărul populației, a căpătat dezvoltare industria meșteșugărească.

În 1902 populația orașului constituia 14.800 locuitori. Din dealul Ivanos se extrăgea cel mai bun var, cu care se face comerț întins. Orașul Orhei mai deținea fabrici mici de lumânări și mai multe tăbăcării.

În anul 1907 la Orhei este deschis un gimnaziu de fete cu 4 clase, transformat în 1910 în liceu cu 7 clase.

La 25 martie 1918, cei 52 de consilieri ai Zemstvei din Orhei au votat unanim Moțiunea de Unire cu România.

Până în anul 1947 Orhei este centru de județ în componența căruia intrau raioanele Bravicea, Chiperceni, Criuleni, Orhei, Răspopeni, Rezina, Susleni și Telenești. Prin reforma administrativă din 1947 județele sunt desființate și Orheiul devine centru raional.

În 1998 oraşul Orhei a devenit reşedinţa judeţului Orhei.  În 2001, odată cu revenirea la raioane în calitate de unități teritorial-administrative, orașul Orhei capătă statut de centru al raionului omonim.

Astăzi, Orhei este al 9-lea oraș ca mărime din Republica Moldova, cu o populație de 33 600 de locuitori, conform ultimului recensământ din 2014.