Osmanlı İmparatorluğu’nun zirveye ulaştığı ve adı tarihe Muhteşem Süleyman olarak geçen Kanuni Sultan Süleyman’ın Sadrazamı Rüstem Paşa tarafından, yine mimaride zirve isimler arasında anılan Mimar Sinan’a 1553 (h. 960) tarihinde, o dönemin ismiyle Rodoscuk kasabasına hediye ettiği en önemli eserlerinden biridir. Kurulduğu günden itibaren küçük bir kasaba olan Rodoscuk sosyo-ekonomik açıdan hızlı bir gelişme izlemiş, bölge için taşıdığı stratejik önemini giderek artırmıştır. Cami, medrese, kütüphane, çifte hamam, bedesten, kervansaray ve imaretten oluşan Rüstem Paşa Külliyesi, bir Osmanlı şehrinin başlıca ihtiyaçlarını karşılayabilecek donanıma göre tasarlanmıştır. Bazı kaynaklarda Külliye kapsamında Debbâğhane (tabakhane) ve Tuzhane de anılmaktadır.

Yapılardan sadece caminin tarihi ve yaptıranı hakkındaki bilgi taç kapıdaki iki kitâbeden öğrenilmektedir. Sülüsle yazılmış ilk kitabede Rüstem Paşa’nın adı ve 960 (Miladi 1553) tarihi yazılıdır. Cami, günümüze kadar çeşitli tarihlerde büyük çaplı onarımlar yaşamıştır. Bunlardan en önemlisi H. 1257 (Miladi 1841) tarihinde Sultan Abdülmecid tarafından yaptırılmıştır ve bu tarih caminin önündeki kitabede de kayıtlıdır. Vakıflar Genel Müdürlüğü’nce yayımlanan Cumhuriyetin 50. Yılında Vakıflar isimli eserde ise Rüstem Paşa Camii’nin 1955 ve 1971 yıllarında onarıma tabi tutulduğuna dair bilgi vardır. Rüstem Paşa Medresesi, kıble duvarına paralel, 16×26 metre boyutlarında, açık avlulu, dikdörtgen planlı olan Medrese binasının ana kütlesi ve kare planlı dışa taşkın dershanesi bulunmakta, caminin kot seviyesinden 5.5 metre aşağıda yer almaktadır. 1596-1597 yılından itibaren görev yapan müderrise günlük 50 akçe maaş ödendiği için ellilik medreseler statüsüne dahil olan Medrese’de müderrisin yanı sıra, bir danişmend, bir muallim ve bir muallim halifesi görev yapıyordu. Zaman içinde bakımsızlıktan dolayı harap olan medrese 1880 yılında meydana gelen bir zelzele neticesi tamamen yıkıldı, üzerine Redif Binbaşı Rıza Bey tarafından iki katlı ahşap bir okul inşâ ettirildi, dershanesi bir süre sonra aşevine dönüştürüldü, bir dönem rüşdiye ve idâdî olarak kullanılmış, daha sonra bu yapı Cumhuriyet İlkokulu adıyla eğitim hizmeti vermiştir.

Medrese’nin doğu duvarına bitişik olarak caminin sol yanında ve ön cephesine kadar uzanan alanda kadınlar ve erkekler için ayrı olarak inşâ edilen Çifte Hamam, Tekirdağ’ın iki yıllık Yunan işgali (1920-1922) sırasında iç bölümlerinin tamamen yıkılması sonucu büyük ölçüde harap oldu, sonraki dönemde uzun yıllar boyunca tuz deposu ve zahire ambarı olarak kullanılmıştır. Günümüzde bu eser, özel şahıs mülkü olup, süpermarket olarak kullanılmaktadır. 1987 yılında Vakıflar Genel Müdürlüğü tarafından, hamam ile cami arasında kalan bahçeye 24 dükkan, cami ile debbağhaneler bölümü arasında kalan yerde Tekirdağ İl Özel İdaresi tarafından 24 dükkan yaptırılmış, bu dükkanların büyük bir bölümü kiraya verilmiştir.

Caminin batısında yer alan bedesten her ne kadar Rüstem Paşa’nın adıyla anılsa da, vefatından yedi yıl sonra eşi Mihrimah Sultan tarafından inşâ ettirilmiştir. Ancak yine eşinin bir vefa örneği olarak Rüstem Paşa adına Küllliye’nin vakfına dahil edildi, böylece Rodoscuk kasabasının ilk çarşısı olma unvanını elde etti. Bir dönem içi mobilyacılar çarşısı olarak da kullanılan Bedesten’in dışına ilave edilen dükkanlarla birlikte Tekirdağ Belediyesi tarafından şehir esnafına kiraya verilmektedir. Ayrıca, yine Tekirdağ Belediyesi tarafından 2008 yılında hayata geçirilen Bedesten ve Çevresi Koruma ve Yaşatma Projesi çerçevesinde, Bedesten yanında bulunan ve tarihi dokuyu büyük ölçüde olumsuz yönde etkileyen dükkanlar ve hal yıkılmış, gerçekleştirilen çevre düzenlemesiyle tarihi yapı daha görünür hâle getirilmiştir. Rüstem Paşa Külliyesi içinde yer alan kervansaray, han, imaret ve kütüphane ise günümüze kadar gelememiştir.