Het echtpaar Cethron en Eufrosina is al jaren kinderloos en dit tot groot verdriet van de man en de vrouw. Ten einde raad gaat de echtgenoot op bedevaart naar Myra om Nicolaas te verzoeken een wonder te verrichten, dat zijn vrouw in verwachting raakt. Bij zijn vertrek uit Myra neemt de man een reliek van Nicolaas mee. Als hij weer thuiskomt vraagt de echtgenote aan haar man of hij een kapelletje wil bouwen en dit aan Nicolaas toe gaat wijden. De man doet dit vol overgave. Negen maanden nadien, op 6 december, bevalt de vrouw van een zoontje. Het kind krijgt de naam Adeodatus. Deze naam staat voor “door God gegeven”.
Zeven jaar later is Adeodatus gegroeid tot een flinke jongen. De streek waarin hij met zijn ouders woont is heel onrustig en op een dag vallen vijandelijke troepen hun gebied binnen. De aanvallers zijn Agareners, ook genoemd Hagarenen en Hagarieten. Zij vormen een Arabische stam en zijn machtige nomaden, die veelal verblijven ten oosten van Israël. De binnendringers vernielen veel en nemen mensen mee als slaven, zo vergaat het ook de jonge Adeodatus.
Adeodatus wordt slaaf bij Marmorinus; de Moorse koning van de Agareners. De jonge krijgt de opdracht als wijnschenker te werken en wordt daartoe opgeleid. Wat later wordt het weer 6 december en Adeodatus vertelt zijn meester over de heilige Nicolaas en het feest ter herdenking aan de voormalige bisschop van Myra. Vervolgens vraagt de jonge wijnschenker aan zijn meester of hij vrij mag worden. Dit wordt hem geweigerd en onmiddellijk erna steekt een zware storm op. Het paleis van de koning wordt flink geteisterd. De sterke wind voert de jongen mee en hij komt terecht vóór de deur van het kapelletje dat zijn vader heeft gebouwd.
Dit verhaal is opgetekend in de 9e eeuw door Johannes Diaconus/Johannes Hymonides in de Latijnse “Vita S. Nicolai”. De legende wordt ook genoemd “het verloren knaapje”.