Rozlohou najväčšia obec na Kysuciach má v súčasnosti prvú písomnú zmienku datovanú rokom 1662, no jej existencia sa dá odvodiť už z urbára v roku 1635. Vznikla vyčlenením sa z pôvodného chotára obce Bystrice v priebehu prvej polovice 17. storočia. Jej zvyšné časti boli v tomto období dosídľované kopaničiarskym spôsobom.
Patrila medzi ne i časť Vychylovka, ktorá sa nikdy nestala samostatnou obcou. Po rozdelení panstva Strečno sa obec stala súčasťou panstva so sídlom v Tepličke. Najstaršou stojacou pamiatkou je kaplnka u Andrisov postavená v roku 1828, pričom jej jadro pochádza ešte spred roku 1818.
Významnou stavbou je kostol sv. Jána Krstiteľa dokončený v roku 1857 zásluhou miestneho farára Lukáša Tormášiho, ale i sochy sv. Jána Nepomuckého pred kostolom a Panny Márie vo Vychylovke. Samostatnou farnosťou sa obec stala v roku 1789. Prvá školská budova tu bola dokončená v roku 1805 na pozemku rodiny Bisahovcov. Pôvodne sa vyučovalo v budove miestnej fary. Takmer všetky staršie obecné písomnosti sú písané v starej slovenčine, čo svedčí o jej výučbe v tunajšej škole. Ťažké obdobie obec zažila počas cholerovej epidémie a následnom masovom odchode miestnych obyvateľov do Banátu.
Počas druhej svetovej vojny v miestnych lesoch operovalo niekoľko partizánskych skupín. V období osemdesiatych rokov bolo na území pôvodných obcí Riečnica a Harvelka vybudované vodné dielo, takže sa toto územie stalo katastrálnou súčasťou Novej Bystrice. Zo spomínaných obcí zostal zachovaný len kostol v Riečnici a nedávno bola dokončená budova kaplnky v Harvelke.
Na oboch miestach sa každoročne striedavo konajú stretnutia rodákov zaplavených obcí. Staršie budovy z týchto dedín boli premiestnené do Múzea kysuckej dediny vo Vychylovke, ktoré sa začalo stavať už v sedemdesiatych rokoch dvadsiateho storočia. Okrem starobylých drevených stavieb z Kysúc je toto múzeum zaujímavé i zachovalou lesnou úvraťovou železničkou.
Tá pre unikátny systém úvratí patrí medzi najzaujímavejšie technické pamiatky tohto druhu na svete. Veľká časť Novej Bystrice sa nachádza v CHKO Kysuce. V katastri obce sú zaujímavé prírodné výtvory: Prahy riečky Vychylovky u Pavelka a Vychylovské skálie u Šudov.
