Aan de overzijde van de mistige bergen en de diep golvende zeeën leefde een koning wiens boomgaard zijn oogappel was. Want in de boomgaard groeide een gouden appelboom. Op een nacht stal een dief de appels. De koning was radeloos en liet zijn stalknecht Ivan de hele nacht op de uitkijk staan. De nacht was half voorbij, toen Ivan plotsklaps een Vuurvogel naar beneden zag duiken, die stiekem van de appels begon te pikken. Hij greep de staart van de vogel, maar die rukte zich los en liet alleen een veer in Ivans hand achter. De koning zond Ivan op zoek naar de magische Vuurvogel. Hij was nog niet ver, toen er plotseling een grote grijze wolf verscheen die hem beloofde te helpen bij het vinden van de dief. Hij gaf Ivan de raad om wat bier met brood en kaas te mengen en dat op de grond te strooien. Toen de vuurvogels dit mengsel aten, werden ze al gauw draaierig en kon Ivan er een pakken en in zijn tas stoppen. Daarna snelde hij op de rug van de wolf terug naar de koning, die al op hem zat te wachten.
Nu had de koning gehoord over een prinses, Jelena de Schone, die voorbij de zeeën woonde. Hij zond Ivan opnieuw op pad, dit keer om het lieflijke meisje te gaan halen. Onderweg werd Ivan echter verliefd op Jelena de Schone en zij op hem. Toen ze de wolf hun dilemma voorlegden, raadde deze hen aan om alles aan hem over te laten. In het paleis van de koning veranderde de grijze wolf zich in een sprekende gelijkenis met de mooie prinses, waarna Ivan de 'wolf-prinses' voor de koning leidde. De koning was dolblij en beval al zijn edelen om de kroning van zijn nieuwe koningin bij te wonen. Maar toen hij zijn bruid kuste, ontmoetten zijn lippen de koude snuit van de grote grijze wolf. De schok was te groot en de oude koning stierf ter plekke. Nu kon Ivan met Jelena de Schone trouwen en zelf koning worden. Wat de Vuurvogel betreft, die werd losgelaten. Maar hij pikte in ieder geval nooit meer aan appels of brood met kaas.
