1948 yılında Metalurgi Rustavi adıyla kurulan kulüp, 2003 yılına dek Erovnuli Liga'da mücadele etmiş ancak ilk kez bu yıl küme düşmüştür. Üç sezon Erovnuli Liga 2'de oynadıktan sonra tekrar küme yükselmiş, 2008 yılında Tbilisi ile birleşme kararı almış ve adını Olimpi Rustavi olarak değiştirmiştir. 2011-12 sezonu başında tekrar Metalurgi Rustavi adını almış ancak 2015'te yeniden ad değişikliğine giderek mevcut adını almıştır.
Gürcistan Sovyet Sosyalist Cumhuriyetinde dört kez şampiyonluk yaşayan Rustavi'nin ayrıca iki Erovnuli Liga, bir de Erovnuli Liga 2 şampiyonluğu bulunmaktadır.
