Phenjan városához egy több mint 400 évvel ezelőtti legenda kötődik. A történet az 1592-ben kitört Imdzsin háború idején játszódik, és központjában egy Kje Vol Hjang nevű kiszeng – a gésák koreai megfelelője – áll. A legenda szerint, amikor a betörő japán csapatok megszállták Phenjan városát, a fiatal lány az elfoglalt területen maradt, és a koreai ellenállás központi szereplője lett. A legendának számos változata van: az észak-koreai feldolgozások koreai Mata Hariként, vagy Zoja Koszmogyemjanszkajaként tesznek említést a kiszengről, míg a dél-koreai feldolgozások az egymásnak ellentmondó elvárások között vergődő és meghasonló nőként mutatják be. A történet végkimenetele azonban minden esetben az, hogy Kje Vol Hjang segítségével egy Kim Üng Szo nevű koreai tábornok – aki egy valós történelmi személy volt – bejutott a megszállt városba, ahol közösen sikerült merényletet elkövetniük a gyűlölt japán helytartó ellen.