Natalja Matwejewa wurde in einer Militärschule ausgebildet. Die Polizistin lebt in Moskau und startet für Dynamo Moskau. Matwejewa gab ihr internationales Debüt bei einem 10-Kilometer-FIS-Rennen im November 2004 als 47. in Muonio. Schon einen Monat später gewann sie in St. Gallen ein Rennen über diese Distanz. Daraufhin gab sie in einer gemischten Nationenstaffel wenige Tage später in Lago di Tesero ihr Weltcupdebüt. Höhepunkt der ersten Saison wurden die Juniorenweltmeisterschaften in Rovaniemi, wo sie Sprint-Vierte wurde. Beim ersten Saisonrennen der Saison 2005/06, einem Sprint in Düsseldorf startete Matwejewa erstmals in einem Einzelweltcup. Sowohl in diesem Einzel wie auch im folgenden Team-Sprint kam sie auf dritte Plätze. In der Folgezeit spezialisierte sich die junge Russin auf Sprintrennen und trat nur selten in Distanzrennen an. Bei den Juniorenweltmeisterschaften 2006 in Kranj gewann sie hinter Astrid Jacobsen Silber im Sprintrennen. Zu Beginn der Olympischen Spiele in Turin wurde sie aufgrund erhöhter Hämoglobinwerte mit einer fünftägigen Schutzsperre belegt.[1] Nach Ablauf der Sperre startete sie im Sprintwettbewerb, wo sie den 30. Platz belegte. In der Folgesaison erreichte sie beim Saisonauftakt in Düsseldorf erneut als Zweitplatzierte im Sprint eine Topplatzierung. Im Dezember 2007 startete sie erstmals im Eastern-Europe-Cup. Dabei holte sie in Krasnogorsk zwei Siege. Im Januar 2007 gewann sie in Syktywkar als Sprintsiegerin ihren ersten Titel bei russischen Meisterschaften. Im Sprint-Gesamtweltcup der Saison 2006/07 belegte sie hinter Virpi Kuitunen und Petra Majdič den dritten Platz. In der Gesamtwertung des Eastern-Europe-Cups wurde sie Sechste. Zu Beginn der Saison 2007/08 startete sie wieder sehr erfolgreich in Düsseldorf in die Saison. Sie gewann mit dem Sprintrennen ihren ersten Weltcup und wurde mit Natalja Korosteljowa Zweite im Teamsprint. Es folgten in der Saison weitere Top-Zehn-Platzierungen darunter ein dritter Platz zusammen mit Jewgenija Schapowalowa im Teamsprint in Liberec und ein zweiter Rang im Sprint in Lahti. Beim Eastern-Europe-Cup in Krasnogorsk siegte sie zweimal. Die Saison beendete sie auf dem vierten Rang in der Sprintwertung und den sechsten Rang im Eastern-Europe-Cup. Ende März 2008 wurde sie erneut russische Meisterin im Sprint.
Am 8. April 2009 gab die FIS bekannt, dass Matwejewa während des Weltcups im Januar im kanadischen Whistler bei einer Dopingkontrolle positiv auf das Blutdopingmittel EPO getestet worden ist.[2] Im Dezember 2009 wurde Matwejewa rückwirkend ab Januar 2009 für zwei Jahre wegen Dopings gesperrt.[3] Der russische Skiverband kündigte darauf hin an, gegen diese Entscheidung Einspruch beim Internationalen Sportgerichtshof CAS einzureichen.[4] Nach Ablauf der Sperre nahm sie zu Beginn der Saison 2011/12 wieder am Skilanglauf-Weltcup teil. Dabei erreichte sie in Düsseldorf im Sprint den dritten und im Teamsprint den zweiten Rang. Es folgten in der Saison weitere Platzierungen unter den ersten Zehn darunter ein zweiter Rang im Sprint in Davos und ein dritter Platz in Otepää. Im Dezember 2011 holte sie in Krasnogorsk ihren fünften Sieg im Eastern-Europe-Cup. Am Ende der Saison belegte sie den fünften Rang im Sprintweltcup. In der folgenden Saison konnte sie ihre starken Resultate im Einzel nicht wiederholen. Ein zweiter Platz im Teamsprint in Sotschi war ihre beste Saisonplatzierung. Bei den nordischen Skiweltmeisterschaften 2013 im Val di Fiemme kam sie auf den 21. Platz im Sprint und den siebten Rang im Teamsprint. Auch in der Saison 2013/14 erreichte sie meist nur Resultate im Mittelfeld. Bei den Olympischen Winterspielen 2014 in Sotschi errang sie den 20. Platz im Sprint. Nach zwei Siege beim Eastern-Europe-Cup in Werschina Tjoi zu Beginn der Saison 2014/15, kam sie im Weltcup dreimal unter die ersten Zehn, darunter Platz zwei im Sprint in Rybinsk. Im Eastern-Europe-Cup belegte sie einmal den zweiten Platz und zweimal den ersten Rang. Die Saison beendete sie auf dem neunten Platz im Sprintweltcup und den ersten Platz in der Gesamtwertung des Eastern-Europe-Cups. Zu Beginn der Saison 2015/16 kam sie auf den 40. Platz bei der Nordic Opening in Ruka. Im weiteren Saisonverlauf erreichte sie bei Weltcupsprints drei Top-Zehn-Resultate. Dabei wurde sie Dritte in Drammen und belegte zum Saisonende den 15. Platz im Sprintweltcup. Nach Platz vier im Weltcupsprint in Ruka und Rang sechs im Sprint in Davos zu Beginn der Saison 2016/17, siegte sie im Sprint beim Alpencup in Goms und zweimal im Sprint beim Eastern-Europe-Cup in Krasnogorsk. Im Januar 2017 gewann sie im Weltcup in Toblach jeweils im Sprint und zusammen mit Julija Belorukowa im Teamsprint. Bei den nordischen Skiweltmeisterschaften 2017 in Lahti holte sie zusammen mit Julija Belorukowa die Silbermedaille im Teamsprint. Zudem errang sie den neunten Platz im Einzelsprint. Ende März 2017 wurde sie russische Meisterin im Sprint. Die Saison beendete sie auf dem 30. Platz im Gesamtweltcup und auf dem siebten Rang im Sprintweltcup.
In der Saison 2018/19 errang Matwejewa mit zwei Siegen den dritten Platz in der Gesamtwertung des Eastern-Europe-Cups. Im Weltcup belegte sie mit neun Platzierungen in den Punkterängen den 46. Platz im Gesamtweltcup und den 21. Rang im Sprintweltcup. Beim Saisonhöhepunkt, den Nordischen Skiweltmeisterschaften 2019 in Seefeld in Tirol, lief sie auf den 24. Platz im Sprint.
Im Dezember 2017 wurde Matwejewa gemeinsam mit zehn weiteren russischen Sportlern lebenslang für die Olympischen Spiele gesperrt.[5]
In bislang 125 Weltcuprennen kam sie 36-mal unter die besten 10, 12-mal auf das Podium (Stand: Saisonende 2018/19).