Det var en gang, ved siden av en gammel borg, en viltvoksende hage. Den lå inneklemt mellom skogen og borgen, og var godt gjemt mellom høye tette trær. Hadde du sett den ville du trodd at den var helt forlatt. Men at den var forhekset, det var helt sikkert. Her og der stod det statuer av stein, dekket av tykk is og snø både sommer som vinter. Noen statuer lå veltet i snøen, og alle ansiktene hadde det samme ulykkelige uttrykket i øynene. Hadde du våget deg enda nærmere ville blodet frosset til is i årene på deg. For skikkelsene var ikke statuer, men forsteinede mennesker, dekket av is. Unge gamle, hertug og fant. Alle som hadde kommet i nærheten av Slott Nådeløs, og Den Onde Kotsjej.
Slottet var trollmannens uhyggelige tilholdssted, og hans ubarmhjertige magi strakte seg ut fra slottsmurene som kalde mørke skygger. Samme hvor sola befant seg på himmelen, så ble den dekket av skyggene, fra nord til syd, fra øst til vest. Det var ingen barn å se blant statuene. Kotsjej holdt dem alle som fanger inne i slottet, slik at han kunne nyte deres latter og lek, sang og dans, eller bare synet av dem slik en katt nyter synet av gullfisk i en dam.
En kald vinterdag forvillet en ung gutt seg inn i hagen. Det var prins Ivan. Han hadde vært ute på jakt og var på vei hjem, men det var et så vakkert lys på himmelen at han så mer opp enn hvor han gikk. De bleke stjernene funklet i kulda, og etter en stund oppdaget han at han var kommet til et sted han aldri hadde vært før. Da plutselig, som en ildtunge fra en dragemunn, skjøt noe gyllent forbi øynene hans, steg opp mot himmelen, for så å lande i snøen like ved. Det var en flammefarget fugl som fikk solstrålene til å samle seg slik at snøen smeltet under henne der hun satt. Ivan gjemte seg bak et tre for ikke å skremme henne. Hun steg til værs igjen, danset over hagen, og om det var noe som kunne mildne følelsen av uhygge måtte det være ildfuglen som fløy kveldsrunden sin i skogen. Prins Ivan stod som fjetret og beundret fuglens fart og ynde der hun beveget seg i sollyset, mens en svak bris fikk fjærene hennes til å dirre. Men da hun stoppet et øyeblikk, kastet han seg fram og slo armene rundt henne. "Der har jeg deg!" ropte han. "Vent til vennene min ser hva jeg har fanget!". Ildfuglen kjempet for å komme seg løs, men greide det ikke. "Slipp meg!" skrek hun. "Ha medlidenhet med meg. Jeg dør hvis jeg ikke har frihet til å fly" Dette rørte ham, og med den ene hånden strøk han henne forsiktig over fjærdrakten, men med den andre satte han henne forsiktig med på bakken. "Jeg ville aldri funnet på å gjøre deg noe vondt", sa han. "Men da jeg så deg, syntes jeg du var så vakker at jeg mest av alt ønsket å ta deg med hjem til slottet mitt". Ildfuglen så lenge på ham, så sa hun langsomt "Du er et godt menneske, og du kommer ikke til å angre på at du lot meg gå. Du tror jeg er svak, men egentlig er jeg en mektig fugl. Se her, ta denne!" Hun plukket en flammerød fjær fra brystet sitt, og holdt den fram mot ham. "Trenger du hjelp noen gang, så kall på meg, og jeg kommer med det samme". Dermed fløy hun opp, og straks etter fløy hun under himmelen som en fugl Føniks.
Ikke før hun var forsvunnet hørte prins Ivan stemmer, og straks kom det en rekke hvitkledde barn, tolv i tallet, som lekte og danset foran øynene hans. Men noe var galt. Hele tiden kastet de engstelige blikk mot slottet og ansiktene deres ble sørgmodige, og hver gang de kom borti en av statuene, kastet de seg vekk og var helt utrøstelige. Prins Ivan kom fram fra skjulestedet sitt for å se bedre, og da barna fikk se ham ble de rådløse og redde. "Ikke løp deres vei!" bad han. "Jeg skal ikke skade dere". Han gikk bort til dem. "Du må skynde deg vekk herfra", sa en liten gutt på samme alder som han selv. "Vi er alle fanger i slottet til Kotsjej". "Han slipper oss ut en gang om dagen, slik at vi kan få frisk luft, men det er som om vi er lenket fast til slottsmuren, vi kan ikke rømme". "Du er i fare", sa en annen. "Gå nå før Kotsjej oppdager deg, og forvandler deg til stein og tårene dine til is." "Ser du de statuene der?", fortsatte ei lita jente. "Blant dem står alle som har forsøkt å redde oss". "Der borte står foreldrene mine". Hun pekte på to statuer som stod litt i utkanten av hagen. I det samme begynte en klokke å slå dystert innefor slottsmurene, og barna gikk mot slottet med langsomme, slepende skritt. "Glem oss alle sammen", hørte han dem hviske, mens slottsporten lukket seg etter dem. "Nei, ikke forsvinn!" bønnfalt Ivan, og rusket i porten. Og, den åpnet seg igjen! Ut strømmet, demoner, nisser, skrømt og troll.
Fryktinngytende beist med hårete kjaker og grisetryner, noen med hoggtenner, andre med krumme klør som krafset borti Ivans klær og hud. De omringet ham fullstendig, og gjorde det umulig for ham å unnslippe. Like etter kom Kotsjej - så høy og ruvende at han måtte bøye hodet under trekronene. Det lange håret og skjegget hans var dekket rimfrost, ansiktet var mørkt. "Jasså, nok en inntrenger!" buldret han. "Hva gjør vi med slike som ham?" "Forvandler ham til stein! Forvandler ham til stein!" Hylte undersåttene hans. "Og tårene til is, og tårene til is". Gjør det, gjør det, herre og mester, så vi kan skjerpe tennene våre på ham, og klørne med" "Så bli til stein!", tordnet Kotsjej.
Ivan visste ikke om det var trolldom eller frykt som grep fatt i leggene hans og tappet armene for styrke. Han ble fylt av en isende kulde, men mot hjertet lå ildfuglens fjær, og med all den styrken han eide tok han fatt i den og svingte den mot Kotsjej. "Allerede?, hørtes en stemme. "Trengte du min hjelp så snart?" Og der kom ildfuglen mot ham. Halefjærene hennes bruste bak henne som et glødende slep. "Hallo, min kjære hoiet Kotsjej. "Snart har jeg deg, og da skal jeg putte deg i et bur, og henge deg i vinduet så du kan synge for meg hele dagen". Prins Ivan ble skrekkslagen, og angret på at han hadde bedt henne om hjelp. Hun var i fare nå på grunn av ham. Men hun svarte ganske rolig; "Jasså du vil fange meg og ha meg til å synge for deg. Men hvis jeg synger, så skal du danse". Hun åpnet vingene, og rørte dem så vidt.
Plutselig begynte alle Kotsjejs demoner å vagge rundt. Så sjanglet de rundt med ristende skuldre og viftende armer, i en slags uskjønn, forvridd dans. "Dans, Kotsjej!" kommanderte Ildfuglen, og ikke engang den store trollmannen greide å stå imot. De voldsomme føttene hans begynte å stampe, så hoppet og bykset de rundt. Hodet hans vinglet fra side til side, hendene hans ristet seg nesten løs fra de lange armene. Han hoppet og spratt som en mann full av glede, men ansiktet hans var forvridd av sinne, og han ropte forbannelser over denne fuglemakten som tvang ham til å danse videre og videre. Demoner, nisser, skrømt og troll gryntet og snøftet. Musklene deres verket, men de greide ikke å stoppe. De løp og snublet i hverandre mens de tryglet og bad trollmannen om å få en slutt på deres lidelser. De danset til de ikke hadde pels igjen på føttene. Til slutt var de helt utmattet, og endelig gav ildfuglen dem lov til å hvile.
De sank sammen på stedet, og falt straks i en dyp søvn. Alle, unntatt Kotsjej. Han lå stille og fulgte Ildfuglen med øynene, men hun viste ikke det miste tegn på redsel. Ivan trakk kniven, løp mot trollmannen for å drepe ham, men Kotsjej bare blottet tennene i et hånlig smil. "Tro ikke at du kan drepe meg," snerret han. "Jeg har gjemt sjelen min utenfor kroppen, på et hemmelig sted." Ivan snudde seg mot Ildfuglen. Han visste ikke hva han skulle gjøre, og Ildfuglen hvisket fort; "Finn sjelen, Ivan og ødelegg den, så blir trolldommen brutt" Jeg har oppdaget noe som kanskje kan sette deg på sporet. Noe rundt og hvitt i et hult tre. Adjø med deg nå, jeg drar min vei".
Hun fløy, og han løftet hånden til farvel. Så begynte han å undersøke det ene treet etter det andre. De var alle friske. Men så kom han til et som var dødt, det så ut som om lynet hadde slått ned i det. I den hule stammen lå et stort, hvitt egg, omtrent like tungt som et manns hjerte. "Ikke rør det, det er mitt!" brølte Kotsjej, og kravlet mot Ivan mens han viftet med de knoklete hendene sine. Men Ivan løftet egget over hodet og slengte det i bakken av all sin kraft. En gul svovelstinkende eggeplomme rant utover og ødela bakken for all tid. Med et redselsskrik rullet Kotsjej rundt på bakken.... og forsvant. Kroppen hans, grusomheten hans og all den onde magien gikk opp i røyk.
Da Ivan så seg rundt, var ikke et eneste lite troll å se. Og nå åpnet portene seg enda en gang, knirkende på rustne hengsler, og skyggene fra nord, syd, øst og vest forsvant på et blunk, mens alle barna som hadde vært fanger i slottet kom løpende ut. Og statuene var igjen levende mennesker av kjøtt og blod, og de stod der med åpne armer for å ta imot alle barna og løfte dem opp i armene sine. "Slott Nådeløs finnes ikke lenger", sa Ivan. "Nå heter det Ildfuglens borg". Etter dette kalte alle folk slottet for Ildfuglens borg, og når vesthimmelen rødmet i solnedgangen og viste en stripe av gull mellom slottspirene, kunne ingen være sikre på om det var Ildfuglen som fløy forbi, eller sola som lyste i øynene deres.