Z dôvodu, že sa nezachovali žiadne písomné doklady o známkach života prvých usadlíkov, je ťažko povedať, kedy sa v Novej Sedlici objavili prví ľudia. Konkrétne archeologické nálezy zo susednej obce Ulič svedčia, o tom, že človek tu bol od mladšej doby kamennej – eneolite. O existencii a vôbec o vzniku obce sa dozvedáme zo spomienok ľudí, ktoré sa formou povestí a legiend prenášali z generácie na generáciu.
Prvá verzia o existencii obce je pod názvom Stražnica – Storožnica, ktorej obyvatelia mali za úlohu brániť horské priesmyky pred nájazdami Tatárov. To znamená, že ak naozaj jestvovala táto dedinka, prví ľudia tu žili už na začiatku 13. storočia.
Druhá verzia, na základe spomienok starých ľudí je, že časť ľudí opustilo starú obec, ležiacu niekde na hrebienku – Rozdiel a postavili si nové domy v doline pri Zbojskom potoku. Postupne sa tu presťahovali všetci ľudia z kopca a hôr. Novú obec nazvali Nová Sedlica (pôvodne od slova selo – obce). Skromné historické pramene túto skutočnosť potvrdzujú. V roku 1567 sa medzi zdanenými obcami humenského panstva spomína obec Rozdiel (Rozcell), kedy bol uskutočnený prepis port humenského panstva. Na základe listiny z roku 1600 sa konkrétne dozvedáme, že v Rozdieli stálo 6 domov a údaj z roku 1612 hovorí, že v obci žili 2 šoltýsi, 9 poddaných a 5 železiarov. Zároveň sa spomína, že obce nemala svojho kňaza. Pre potvrdenie starej legendy o vzniku obce je tiež dôležitý údaj z roku 1630. Z tohto roku sa zachoval súpis obecných obvodov tzv. krajné. Na čele tejto administratívnej jednotky bol krajník. Vtedy krajníkovi Gregorovi Belienskemu patrilo 15 obcí, medzi ktorými je spomínaný Rozdiel, avšak pod názvom Rosczel vel Nouoszelicze. Obec v tomto období patrila k humenskému panstvu, ktorého vlastníkom bola magnátska rodina Drugethovcov.
Pre obec Nová Sedlica bolo tragickým obdobím koniec 17. a začiatok 18. storočia. Život obyvateľov ovplyvnili udalosti protihabsburského povstania a morová epidémia, ktorá sa do týchto končín preniesla v rokoch 1676-1680 z Poľska a trvala do roku 1710. Tieto pohromy priniesli skazu pre obec. Odrazom je zníženie počtu obyvateľstva. Celé 18. a 19. storočie sa nieslo v znamení neúrodnosti, hladu a častej smrti. Pôvodné obyvateľstvo bolo pravoslávneho vierovyznania. V roku 1690 v Stakčíne farári tejto oblasti prijali úniu, t.j. prešli na grécko-katolícku vieru. Od roku 1777 bola v obci vedená matrika.
V roku 1787 mala obec 57 domov, v roku 1828 už 82. Obyvateľstvo sa zaoberalo prevažne poľnohospodárstvom a príležitostnou prácou v lesoch. Pracovala tu píla aj stupy.
Posledným známym vlastníkom bol Rudolf Scherényj, ktorý zdedil všetok majetok v Novej Sedlici v roku 1919 po svojich rodičoch. Počet obyvateľov sa v priebehu 19. storočia veľmi nemenil. Za vlády Márie Terézie a Jozefa II. sa rozvíjal jarmočný ruch, stavba kostolíkov a typických drevených domčekov. Pred 1. svetovou vojnou tu bola postavená úzkokoľajka.
Úplnou katastrofou pre obec bola 1. svetová vojna so začiatkom 28.7.1914. Takmer všetky obytné domy i hospodárske budovy boli zničené. Podľa pamätí ľudí ostali v obci stáť dve nepoškodené budovy – stará drevená cerkva a roľnícky domček. Čo sa týka bývania, ľud býval veľmi jednoducho v drevených domčekoch, ktoré boli pokryté slamou dlážka bola z udupanej hliny. Ťažko pracovali, deti hynuli podvýživou. Jediný lekár bol až v Snine. Ľudia nevedeli čítať a písať. Do školy sa chodilo, len keď doma nebolo čo robiť. No o tom, že im na vzdelaní záležalo svedčí fakt, že si svojpomocne postavili novú murovanú školu v roku 1927 medzi prvými v okrese Humenné. Roky 1918 – 1938 znamenajú rozvoj národnostného slovenského i ukrajinského školstva. Zlepšili sa sociálne i zdravotné podmienky.
Ako druhou úplnou katastrofou bola 2. svetová vojna, ktorej odrazom bol hlad, bieda, utrpenie a choroby. September 1944 zaznamenáva príchod Nemcov. Nová Sedlica sa musela evakuovať. Mladí odchádzajú, ale veľa ich napriek nástrahám ostávajú. Nová Sedlica bola oslobodená Sovietskou armádou 16. októbra 1944. Obyvatelia všetky svoje sily zamerali na obnovu dediny, budovali nové domy, objekty. Ich činnosť narúšali ukrajinsko-poľský Banderovci, ktorí 27. novembra napadli Novú Sedlicu. Navyše obec postihol aj týfus na následky ktorého zomrelo 87 osôb. Postihnutým pomáhali aj lekári z Užhorodu. Našťastie prišla pomoc z úradov v rámci „akcie U-U“ v roku 1960.
Vybudovala sa nová cesta a prebieha výstava nových rodinných domov. Zveľaďovanie obce pokračovalo, bola zavedená elektrifikácia (1959) , začalo sa s výstavbou kultúrneho domu a opravili sa zničené mosty. Miestny rozhlas a prvý samospádny vodovod bol zavedený v roku 1961. Vybudovala sa asfaltová cesta. Prvý autobus sa datuje už od roku 1955 a rok na to sa vybudoval obchod s potravinami.
