Kızkulesi ile ilgili anlatılan ilk hikaye; Ovidiusun kaydettiği bir aşk hikayesidir. Hero ile Leandros adlı iki gencin hüzünlü aşkını anlatan bu hikaye, Heronun kuleden ayrılmasıyla başlar. Hero Afroditin rahibelerindendir ve aşka yasaklıdır.Yıllar sonra Afroditin tapınağında yapılan bir törene katılmak için kuleden ayrılır ve orada Leandros ile karşılaşır. Birbirine aşık olan iki genç, Leandrosun gece kuleye gelmesi ile aşklarını kutsarlar. Kızkulesi her gece iki gencin gizli aşkına ve yasak sevişmelerine tanıklık eder. Leandrosun yüzerek kuleye geldigi fırtınalı bir günde Heronun yaktığı sevda ateşinin feneri söner. Karanlıkta yolunu kaybeden Leandros boğazın sularına gömülür. Sevgilisinin öldüğünü gören Hero da kendini Kızkulesinden boğazın sularına bırakır.
Kavuşamayan aşıklara atfen anlatılan bu hikayeden başka bir de; Kleopatranın sonuna benzer bir sonun anlatıldığı yılan hikayesi vardır. Kehanete göre kralın birine, çok sevdiği kızı onsekiz yaşına geldiğinde bir yılan tarafından sokularak ölecegi söylenir. Bunun üzerine kral denizin ortasındaki bu kuleyi onararak kızını buraya yerleştirir. Kaderin kaçınılmazlığını kanıtlarcasına, kuleye gönderilen üzüm sepetinden çıkan bir yılan, prensesin tenine süzülerek zehrini boşaltır. Kral, kızına demirden bir tabut yaptırarak Ayasofyanın giriş kapısının üstüne yerleştirir. Bugün bu tabutun üstünde iki delik vardır. Yılanın, ölümünden sonra da onu rahat bırakmadığına dair hikayeler anlatılır.
En son anlatılan hikaye ise Osmanlı Dönemi ile ilgilidir. Battal Gazinin askerleri ile Kızkulesine baskın yaparak kuleye saklanan hazinelerin ve Üsküdar Tekfurunun kızını kaçırdığı ile ilgili hikayedir. Battal Gazi tekfurun kızı ve hazinelerini aldıktan sonra Üsküdardan atına atlayıp oradan uzaklaşmıştır. Çokça bilinen Atı alan Üsküdarı geçti lafı bu hikayeden gelir. Bu hikayeden günümüze gelen bir diğer şey de küçük kulemizin ismi ile ilgilidir. Diğer efsanelerdeki prenseslere de atfen Türkler buraya Kız-Kulesi ismini vermişlerdir.
Antikçağda Arkla (küçük kale) ve Damialis (dana yavrusu) adları ile anılan kule, bir ara da Tour Leandros ismi ile ün yapmıştır.Şimdi ise Kızkulesi ismi ile bütünleşmiş ve bu ismi ile anılmaktadır.
