Ըստ լեգենդի`լեգենդի՝ հին Ռուսթավ քաղաքը հիմնադրել է վրացիների նախահայր [[Քարթլոս]]ի այրին և ի սկզբանե Բոստան Քալաքի անվանում է ստացել։<ref>Լեոնտի Մրովելի «Քարթլիական այքաների կյանքը»</ref> Քաղաքի հիմնադրման իրական թվականը անհայտ է, սակայն արդեն մ.թ. IV - V դարերում այստեղ կար բերդ, տաճար և ոռոգիչ ջրանցքներ։ Քաղաքը ապրել է իր ծաղկման շրջանը [[Թամար]] թագուհու օրոք։ Մոտավորապես 1236 թվականին քաղաքը ամբողջությամբ ավերել են [[Մոնղոլյան կայսրություն|մոնղոլները]]։<ref name="advantour">[http://www.advantour.com/rus/georgia/rustavi.htm advantour.com]</ref>
Նոր քաղաքը հիմնադրված է եղել [[1948]] թվականին հին Ռուսթավի սկզբնական վայրի մոտ, քանի որ կառուցվում էր խոշոր մետաղագործական գործարան։<ref name="advantour"/>