После подписания в 1783 году Георгиевского трактата о протекторате России над Картли-Кахети русско-грузинское общение заметно оживилось. В урочище ингушского селения Заур-Ков была основана крепость Владикавказ. Официально Военно-Грузинская дорога начиналась от станицы Екатериноградской, тогда это был город. В то время дорога была единственной транспортной связью двух стран. Современное название — Военно-Грузинская — закрепилось за дорогой после начала её реконструкции русским военным ведомством под руководством Павла Цицианова (1803).
Постоянное сообщение по дороге было открыто в 1799 году, передвижение было весьма трудным — посланный в том году в Картли-Кахети отряд Русской армии под командованием генерала Лазарева прибыл на место через 36 дней. После получения Картли-Кахети подданства России (1801) началось строительство новой, улучшенной Военно-Грузинской дороги. В 1811 году дорога перешла под надзор Управления путей сообщения России, был проведён колоссальный объём работ — сняты откосы, созданы карнизы, сделаны выемки, построены мосты, проведена отсыпка, возведены плотины и дамбы, для предотвращения обвалов — подпорные стены и крытые траншеи и так далее. В 1814 году открыто движение экипажей, с 1827 года — устроена экспресс-почта.
На дороге были устроены 11 станций (следуя из Владикавказа) — Балта, Ларс, Казбек, Коби, Гудаури, Млеты, Пасанаури, Ананур, Душет, Цилкани, Мцхета, далее — Тифлис. На всех станциях имелись помещения для бесплатного ночлега.
В 1837 году была предпринята попытка обойти Крестовый перевал, направив дорогу через Гудамакарское и Гудушаурское ущелья и Квенатский перевал, однако через десять лет, в 1847 году, после проведённых изысканий было решено вернуться на первоначальный маршрут.
