Время основания города неизвестно. Он построен на месте дакийской крепости Петродава, известной также под именем Старого Орхея (молд. Orhei Vechi). Остатки крепости с подземными ходами сохранились до наших дней. Они находятся между сёлами Требужены и Бутучены. Здесь были найдены древние вещи и монеты. Запорожцы называли Оргеев Иргеевым и Игреевым; на Руси он был известен в старину под названием Орыга или Орыгова.
Оргеев воспет в гайдукских песнях как край вольности. До 1812 года здесь была резиденция турецких сардарей, управлявших северной частью Бессарабии. В 1835 году местечко Орхей переименовано в уездный город Оргеев. Перед началом Второй мировой войны Орхей был домом для многих евреев.
Во время Ясско-Кишинёвской операции город был практически полностью уничтожен артиллерийским огнём и бомбёжками. После окончания войны он был отстроен заново.