Za założyciela miasta uważa się wspomnianego gruzińskiego władcę Wachtanga Gorgasali. Wobec tego początki Tbilisi datuje się na V wiek. Jednak badania archeologiczne wskazują na istnienie osad już w czasach neolitu. Z kolei w erze brązu na miejscu dzisiejszej metropolii żyła wysoko rozwinięta społeczność. Znajdowana biżuteria i ceramika świadczy o kontaktach handlowych z greckimi koloniami na czarnomorskim wybrzeżu i Rzymem. Istnieją dowody, że także nazwa miasta ma o wiele starsze korzenie. Mianowicie, już rzymski geograf Kastoriusz umieścił na swej mapie - pomiędzy Mcchetą i Rustawi – miejscowość „Tfilado”. Już wtedy istniała twierdza Narikala, która dziś dumnie góruje nad czerwonymi dachami tbiliskiej starówki.
W V wieku Wachtang Gorgasali odbił miasto z rąk Persów i zdecydował o przeniesieniu stolicy z pobliskiej Mcchety. Zanim zdążył
wcielić te plany w życie, zginał w wieku 50 lat walcząc z perskim najazdem. Tbilisi stało się faktyczną stolicą Gruzji na początku
VI w., czyli za panowania króla Daczi I Udżarmelego, który w ten sposób wypełnił wolę swego ojca. Pierwszy kompleks królewskich pałaców stanął na miejscu dzisiejszego placu Metechi w dzielnicy Abanot-Ubani.
O wyborze Tbilisi jako stolicy zapewne zdecydowało strategiczne usytuowanie. Miasto leży na skrzyżowaniu dogodnych szlaków. Jedne biegną z Azji nad Morze Czarne, na osi wschód-zachód, np. Szlak Jedwabny. Inne szlaki przechodzą w poprzek Wielkiego Kaukazu a właśnie niedaleko Tbilisi bierze swój początek najbardziej dogodna trasa przecinająca góry – Gruzińska Droga Wojenna. O wadze tego miejsca wiedziało wielu władców, którzy wielokrotnie wysyłali swoje armie na podbój Tbilisi.
Historia Tbilisi to czas przeplatania się okresów zagłady i odbudowy. Przez 1500 lat bycia stolicą, Tbilisi doznało wielu
niszczycielskich najazdów. W tym czasie około 30 razy gruzińska stolica doświadczała tego co Warszawa w 1944 r. Aż 30 razy miasto było kompletnie rujnowane a cała ludność brutalnie mordowana przez wrogie armie. Ostatnia taka apokalipsa rozegrała się w Tbilisi w 1795 r., gdy hordy perskiego szacha zalały wschodnią Gruzję. Po każdej takiej agresji miasto odradzało się na nowo niczym Feniks z popiołu.
Pod koniec VI w. Tbilisi przeszło we władanie Persów. Ich panowanie zakończył podbój Bizantyjczyków wspieranych przez armie
Chazarskie w 627 r. Przez kolejnych sto lat rządy w Tbilisi przejmowali na zmianę Arabowie, Gruzini i Chazarwie. Rok 853 rozpoczął długie – bo trwające aż 200 lat – panowanie Arabów, którzy utworzyli Kalifat Tbiliski. Z rąk Arabów miasto odbili Turcy Seldżuccy i dopiero w 1122 r. za panowania Dawida Budowniczego (Agmashenebeli) Gruzinom udało się odzyskać swoją stolicę. W okresie panowania obcych potęg siedziby gruzińskich królów mieściły się w innych miastach, np. w Kutaisi oraz Uplisciche.
Dzięki działalności Dawida Budowniczego Tbilisi stało się stolicą zjednoczonej Gruzji, która składała się z ziem dwóch dawnych królestw, tj. na wschodzie Iberii oraz Kolchidy na zachodzie. Ówczesne państwo a wraz z nim jego stolica wchodziły w „złoty wiek”. W mieście mnożyły się okazałe budowle a Tbilisi stało się głównym ośrodkiem życia gospodarczego i kulturalnego w tej części Świata. Miejskie granice zostały znacznie rozszerzone a wewnątrz żyła wieloetniczna społeczność licząca ok. 80 tysięcy mieszkańców.
Okres tbliskiej prosperity skończył się wraz z najazdem Mongołów w 1236 r. Sto lat później, na krótko, Tbilisi znów stało się stolicą zjednoczonej Gruzji. W kolejnych stuleciach Tbilisi stało się przedmiotem ostrej rywalizacji między Persją i Turcją. W okresach, gdy obie potęgi mocno osłabiały się nawzajem, przejściowo odradzała się władza gruzińska w Tbilisi. Krwawe dysputy presko-tureskie wyciszył traktat z 1723 r., zgodnie z którym Tbilisi znalazło się w perskiej strefie wpływów. Nastał wówczas okres względnego spokoju i rozwoju, po którym pozostały wyraźne wpływy kultury perskiej w tbiliskiej architekturze i literaturze.