Urodziła się w 1984 roku. Pochodzi z Augustowa, wychowywała się w Białymstoku, w Supraślu ukończyła liceum plastyczne. Studiowała na Akademii Pedagogiki Specjalnej, pracuje w Bemowskim Centrum Kultury, gdzie zajmuje się edukacją artystyczną i animacją społeczności lokalnej.
Wydała dwie płyty w ramach projektu Nathalie and The Loners: "Go, Dare" (2009) i "On Being Sane in Insane Places" (2012). O pierwszym z tych albumów pisała na portalu Screenagers Kasia Wolanin:
"Go, Dare" prezentuje dwa oblicza Natalii Fiedorczuk. W pierwszym wokalistka jest typową singer/songwriterką na zachodnią modłę. (...) [Fiedorczuk] wypada dostojnie i przekonująco niemal w każdej swojej kompozycji. Drugą stronę płyty Nathalie & The Loners poniekąd zapowiada już nieco psychodeliczny opener krążka (...) "Vod", "Sunday" i przede wszystkim fantastyczne "It Is So" pokazują Natalię Fiedorczuk jako błyskotliwą interpretatorkę dream-popowej elektroniki bardziej spod znaku Apparata niż starszych klasyków gatunku.
Od 2008 roku jest wokalistką i autorką tekstów zespołu Happy Pills, z którym wydała płytę "Retrosexual" (2010). Współpracowała także z zespołami pl.otki i Orchid. Od 2011 roku jest członkinią folkowego projektu znanego z zespołu Ścianka Maćka Cieślaka PTKCSS, od 2012 roku zaś występuje z grupą Urlatori e Łobuzzi, która wykonuje covery włoskich przebojów sprzed półwiecza.
Jest autorką muzyki do filmów "Powrót", "Dżej Dżej", "Mów mi Marianna" oraz "53 wojny". Stworzyła muzykę do spektakli Anny Smolar: "Dybuka" (Teatr Polski w Bydgoszczy), "Henrietty Lacks" (Nowy Teatr w Warszawie) i "Kopciuszka" (Stary Teatr w Krakowie).
Wszechstronnie utalentowana artystka jest również autorką albumu "Wynajęcie", wydanego w 2012 roku przez Fundację Bęc Zmiana. Fiedorczuk udokumentowała w nim proces poszukiwania mieszkania w Warszawie.
W 2016 roku, nakładem wydawnictwa Wielka Litera, ukazała się jej debiutancką powieść. "Jak pokochać centra handlowe" wyrasta z osobistych doświadczeń autorki związanych z macierzyństwem i depresją poporodową, ale wykracza poza nie, stając się zapisem rozpadu osobowości. Jak mówiła w rozmowie z Sylwią Szwed dla "Wysokich Obcasów":
Chodzi o taki moment w życiu, który wszystko zmienia. Huragan, który rewolucjonizuje twój światopogląd. I w moim przypadku tym czymś było macierzyństwo. Moja książka jest właśnie próbą konfrontacji z wewnętrznym kryzysem i trudnymi uczuciami izolacji (...).
Kim jestem, kiedy rodzę dziecko? Czy wciąż sobą? Czy może wszystkim: matką, żoną, kucharką, opiekunką, przytulającymi ramionami, zaharowaną panią domu, tylko właśnie nie sobą? Fiedorczuk pisze o izolacji, rozczłonkowaniu, rozczarowaniu, ale bez użalania się nad narratorką, raczej z ironią, niż przesadną tkliwością.