Hero ile Leandros adlı iki gencin hüzünlü aşkını anlatan bu hikaye Hero'nun kuleden ayrılmasıyla başlar.Hero Afrodit'in rahibelerindendir ve aşka yasaklıdır.Hero yıllar sonra Afrodit'in tapınağında yapılan bir törene katılmak için kuleen arılır ve orada Leandros ile karşılaşır.Birbirine aşık olan iki genç Leandros'un gece kuleye yüzerek gelmesi ile aşkını kutsarlar.Kız kulesi her gece iki gencin gizli aşkına ve yasak sevişmelere tanıklık eder.Leandros'un yüzerek kuleye geldiği fırtınalı bir gecede Hero'nun yaktığı sevda ateşinin feneri söner.Karanlıkta yolunu kaybeder.Leandros boğazın sularında boğulur.Sevgilisinin öldüğünü gören Hero 'da kendini Kızkulesi'nden boğazın sularına bırakır.

            Başka bir hikaye de :

            Kralın birine çok sevdiği kızı onsekiz yaşına geldiğinde bir yılan tarafından sokularak öleceği 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 yilan prensin tenine süzülerek zehirin boşaltır.Kral kızına demirden tabut yaptırarak Ayasofya'nın giriş kapısının üzerine yerleştirir.Bugün bu tabutun üzerinde iki delik vardır.Yılanın ölümünden sonra onu rahat bırakmadığına dair hikayeler anlatılır.

             Başka bir hikaye de :

             Osmanlı dönemi ile ilgilidir.Battal Gazi'nin askerleri ile Kız Kulesine baskın yaparak kuleye saklanan hazinelerin ve Üsküdar Tekfuru'nun kızını kaçırdığı ile ilgili hikayedir.Battal Gazi Tekfurun kızı ve hazinelerini aldıktan sonra Üsküdar'dan 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 şeyde küçük kulemizin ismi ile ilgilidir.Diğer efsanelerdeki prenseslerede atfen Türkler buraya Kız-Kulesi ismini vermişlerdir.