Roman 1589 yılının haziranında, Kırım’ın Bahçesaray şehrinde başlar. Bahşı Yunus, fakir bir ırgatın oğludur ve gönlünü Çakır Yorgi adındaki bir papazın kızı olan Kaknusia’ya kaptırmıştır. Kaknusia da Bahşı Yunus’u sevmektedir. Bir halk ozanı olan Bahşı Yunus, sevgilisi Kaknusia için dutar adlı çalgısını çalıp türküler söylemekte, onunla gizli gizli görüşmektedir. Başlarda Çakır Yorgi’nin de bu ilişkiye rıza gösterir ancak zamanla kızının bir Müslümanla evlenmesi fikrine karşı çıkar ve kızını bir Hıristiyanla evlendirmek ister. Sözünden caydığı görülmemiş Çakır Yorgi’nin bu kararı hem kızında hem de Bahşı Yunus’ta büyük bir şaşkınlık yaratır. Bahşı Yunus, çareyi Kaknusia’yı kaçırmakta bulur. Fikrini sevgilisi ile paylaşır. Kaknusia bu fikre rıza gösterir. Bir gün gizlice kaçarlar ve Cufutkale’de hem kilisede hem de camide nikah kıydırırlar. Ne var ki Çakır Yorgi, onların peşine adam takmıştır. Bu adamlar Kaknusia’yı ele geçirirler fakat Çakır Yorgi’ye teslim etmek yerine esir olarak satarlar. Bunu öğrenen Bahşı Yunus, eşini kurtarmak için subaşıya koşar. Subaşı bir emir yazdırıp esasen hür olan Kaknusia’nın salıverilmesini ve zararın devlet tarafından karşılanacağını bildiren resmi bir yazı yazdırır ve bu yazıyı Bahşı Yunus’a verir. Bahşı Yunus, eşinin tutulduğu gemi olan Slamander filikasına yetişemez. Filika, biraz evvel yola çıkmıştır. Filikanın peşinden bir kayıkla yetişir ve aşçı yardımcısı sıfatıyla mürettebata dahil olur. Elindeki resmi belgeyi, gemide en güvenilir bulduğu kişiye, Dede Dayı adlı ikinci kaptana gösterir. İkinci kaptan esirci ağaya durumu bildirir. Esirci ağa, Kaknusia’nın serbest kalması için gerekli olan resmi belgeyi yani ıtıknameyi düzenler ve Bahşı Yunus’a teslim eder ancak esiri İstanbul’a kadar serbest bırakamayacağını bildirir. Bahşı Yunus buna rıza gösterir. Talihin çarkı dönmektedir. Karadeniz’de fırtına çıkar ve Slamander filikası batar. Bahşı Yunus, bu gemi kazasında eşinin izini kaybeder. Bir ağaç parçasına tutunup hayatını kurtarır. Kendisiyle beraber birkaç kişiyi daha kurtarmıştır. Bu kişiler denizde kendilerinden geçer ve gözlerini Kaligra’daki bir tekkede açar. Bahşı Yunus, hasta yatağında yatmaktadır. Onun kurtardığı kişiler ise kendilerini Bahşı’nın köleleri olarak tanıtmıştır. Bahşı kendine geldiği gibi Kaknusia’nın izini sürmeye başlar ve İstanbul’a dek gelir. Bu arada Kaknusia, deniz kazasından sağ kurtulmuş ve tekrar esircilerin eline geçip İstanbul’a teslim edilmiştir. Satılmaktan kurtulmak için bir gece yarısı arkadaşı Selma ile kaçan Kaknusia, Evrennik adlı bir yeniçerinin kayığıyla Avrupa yakasından Anadolu yakasına geçer. Bu sırada Kaknusia bayılır. Selma, onu Evrennik’e teslim edip kaçar. Kaknusia’nın güzelliğinden etkilenen Evrennik, onu bir tanıdığına emanet eder. Kısa süre sonra Kaknusia’nın hamile olduğu anlaşılır. İstanbul’da konuştuğu hiç duyulmayan Kaknusia’nın dilsiz olduğu düşünülür. Bundan dolayı Evrennik ona Lâlin adını takar. Lâlin’in hamile olması Evrennik’in hayallerini yıkmıştır ama sevgisi ağır basar ve bu kızla göstermelik bir şekilde evlenir. Böylece ona yardımcı olur. Lâlin’in bir kızı dünyaya gelir. Evrennik onun adını Lalzade koyar. Bahşı Yunus, sevdiği kadının İstanbul’da olabileceğini düşündüğü için yıllarca onu arar. Fakat Bahşı, onun kölelerinden biri olan Gunala tarafından şiddetli bir aşkla sevilmektedir. Diğer köleler Bahşı’yı terk ettiği hâlde Gunala Bahşı’ya daima bağlı kalmıştır ve onunla evlenmeyi kurmaktadır. Osmanlı sarayına giren Gunala, kısa sürede Kaknusia’nın izine ulaşır ve Bahşı’nın ona ulaşamaması için elinden geleni yapar. Evrennik de Bahşı’nın Lâlin’i (Kaknusia) faretmemesi için uğraşmaktadır. Tüm bu rakiplere ve imkânsızlıklara rağmen bir gün Bahşı’nın yolu Kaknusia ile kesişir. Evrennik, iki âşığın yolundan çekilmek üzere Van’a, İran’la savaşmak üzere gider. Yıllarca konuşmayan Kaknusia ise, Sultanahmet Camii’nin hizmete açıldığı günün gecesinde Bahşı ile konuşur. Bahşı ile evlenme hazırlığında olan Gunala, Bahşı’yla Kaknusia’nın aşkla sohbet etmelerine şahit olur. O gece gizli gizli Kaknusia’yı takip eder, evinin civarında kendisini Bahşı’nın kölesi olarak tanıtır, Kaknusia’nın evine girer. O gece Kaknusia ile uzun uzun sohbet eder. Nihayetinde, bu rakibinden kurtarmak için onu öldürür. Sonra kayıplara karışır. Kaknusia’nın ölümü, hem Evrennik’i hem Bahşı’yı delirtir. Kaknusia’nın ölümünden bir yıl sonra, Kulaksız Mezarlığı’nda iki âşık karşılaşır. Birbirinin rakibi olan Bahşı ile Evrennik, aşka dair derin bir sohbete girişir. Sohbetin bir yerinde sevgili yolunda ölmekten söz ederler. Tam bu esnada Gunala sahneye girer. Sevgili yolunda öldürmenin ölmekten daha üstün olduğunu savunur ve Kaknusia’yı öldürdüğünü itiraf eder. Kısa bir zaman sonra üçü, birbirinin boğazını sıkmaya başlar. Nihayetinde her üçü de Kaknusia’nın mezarı üzerinde can verir.
İskender Pala’nın bu romanı, klasik Türk edebiyatı geleneğinin aşk anlayışı çerçevesinde yazılmış bir eserdir. Sevgili, kâinat güzelidir. Âşık, sevgili yolunda canından ve cihandan geçecek kadar delidir. Ayrıca âşığın daima bir rakibi vardır ve onunla mücadele etmek zorundadır. Bu aşk ilişkisi, bedensel dürtülerden mümkün olduğunca soyutlanmış ve idealize edilmiş bir hâldedir. Hatta aşk, Allah’a ulaşmak için bir yoldur. Romanda anlatılan aşk, sevgili ile beraber yaşanan ve mutlu olunan bir olgu değildir; sevgilinin peşinde geçen ve ona ulaşmak için türlü zorluklara katlanılan, acı veren, eziyet eden ve âşığın aklını başından alan bir deneyimdir. Yazar, klasik Türk edebiyatı geleneğindeki aşk ilişkisini Aşk Hikâyesi adlı eserle roman formunda okuyucuya aktarmaktadır. Dolayısıyla bu roman, adeta bir gazel gibi, aşk olgusunun karikatürize edildiği, âşık-sevgili-rakip tiplerinin anlatıldığı bir eserdir.