This article presents the first sustained narratological analysis of the embedded stories in Nikephoros Bryennios’ Material for History. It argues that pleasure in storytelling was a valued feature of Byzantine historiography and that Bryennios’ anecdotes derive their appeal from four interrelated features: eventfulness, tellability, narrativity, and immersion. The article further contends that, by mimicking oral storytelling through rhetorical questions, direct speech, and vivid sensory detail, Bryennios crafts narratives suited to performative settings while preserving a sense of authenticity. It concludes by proposing narratological criteria for identifying and analysing anecdotes across Byzantine historiography and reassessing the role of pleasure in historical writing.