Thbilisi asutajaks peetakse 5. sajandil pKr elanud Kharthli kuningat Vahtang I Gorgasalit. Ta valis selle koha uueks kuninga residentsiks Iveria vana pealinna Mtshetha asemele. Kindlus oli seal olemas arvatavasti juba 4. sajandil eKr.