Natalja Korosteljowa debütierte auf internationaler Ebene im Dezember 2001 bei einem FIS-Rennen in Krasnogorsk. Im Februar 2002 gewann sie im Val di Fiemme über 15 Kilometer ihr erstes Continental-Cup-Rennen. Seit Beginn der Saison 2002/03 wird Korosteljowa regelmäßig im Skilanglauf-Weltcup eingesetzt. In Kiruna erreichte sie im November 2002 als Vierte mit der Staffel ein erstes gutes Weltcup-Ergebnis. In Clusone erreichte sie einen Monat später als Neunte im Sprint erstmals eine Einzelplatzierung in dem Top Ten des Weltcups. Im folgenden Februar wurde sie zusammen mit Aljona Sidko Zweitplatzierte im Teamsprint von Asiago. Bei der folgenden Nordischen Skiweltmeisterschaften im Val di Fiemme gewann sie mit der Staffel die Bronzemedaille und wurde Neunte im Sprint und 15. über 10 Kilometer. Aufgrund einer Schwangerschaft traten Korosteljowas sportliche Bestrebungen zunächst in den Hintergrund und sie brauchte längere Zeit, um ihre alte Form wiederzuerlangen. Zu Saisonbeginn 2007/08 wurde sie in Düsseldorf Zweite im Teamsprint. Ihr bisher einziger Sieg in einem Weltcup-Rennen war in der Folgesaison erneut beim Teamsprint in Düsseldorf, ihre Partnerin war Natalja Matwejewa. Bei der Tour de Ski 2009/2010 war sie Zweite beim Prolog und entschied den zweiten Sprint für sich. Korosteljowa qualifizierte sich ebenso wie ihr Bruder Nikolai Morilow für die russische Skilanglauf-Mannschaft bei den Olympischen Spielen 2010 in Vancouver. Sie kam bei vier Bewerben zum Einsatz und gewann zusammen mit Irina Chasowa die Bronzemedaille im Teamsprint. Mit der Staffel wurde sie Siebte, im Sprint Zwölfte und über die 10 km-Distanz Neunzehnte. Im März 2010 wurde sie in Syktyvkar russische Meisterin über 10 km. Die Saison beendete sie auf den zehnten Rang im Gesamtweltcup und den achten Platz im Sprintweltcup. In der Saison 2010/11 kam sie in Rybinsk mit der Staffel auf den dritten Platz. Bei den Nordischen Skiweltmeisterschaften 2011 in Oslo belegte sie den 32. Rang im Sprint. Zu Beginn der folgenden Saison erreichte sie den 18. Platz bei der Nordic Opening in Kuusamo. Im weiteren Saisonverlauf kam sie in Düsseldorf zusammen mit Natalja Matwejewa auf den dritten Rang im Teamsprint und in Moskau auf den zweiten Platz im Sprint. Zum Saisonende errang sie den 16. Platz im Sprintweltcup. Bei den Nordischen Skiweltmeisterschaften 2013 im Val di Fiemme wurde sie zusammen mit Natalja Matwejewa Siebte im Teamsprint. In der Saison 2013/14 startete sie ebenfalls im Eastern Europe Cup den sie auf den ersten Platz in der Gesamtwertung beendete. Im Weltcup kam sie bei acht Teilnahmen, viermal in die Punkteränge. In der folgenden Saison erreichte sie bei zwei von acht Weltcuprennen Weltcuppunkte.
Korosteljowa ist mit dem früheren Biathleten und heutigen SkitechnikerPawel Korosteljow verheiratet, hat ein Kind und lebt in Rybinsk. 53 Mal konnte sie bislang (Stand:Saisonende 2014/15) Weltcupplatzierungen in den Top Ten erreichen, davon 23-mal im Einzel, 11-mal kam sie bei Rennen aufs Podium, davon zweimal mit der Staffel und viermal im Teamsprint.
2007 Sapporo: 7. Platz Staffel, 10. Platz 10 km Freistil, 11. Platz 15 km Verfolgung, 27. Platz Sprint klassisch, 28. Platz 30 km klassisch Massenstart
2009 Liberec: 10. Platz Sprint Freistil, 35. Platz 15 km Verfolgung
Russland
.svg){kind=small}
Russische SFSR
Düsseldorf
Prag
Val di Fiemme
