Nowosiółka z przysiółkiem Młynówka niegdyś nazywała się
Nowosielce. W okresie międzywojennym nosiła nazwę Nowosiółka Biskupia lub Nowosiółka nad Zbruczem. Wieś leżała na prawym brzegu Zbrucza i sąsiadowała z Zalesiem i Kurdyńcami.
Miejscowość historycznie bardzo stara. W starych aktach spotyka się wzmianki o ludziach z Nowosiółki w latach 1448, 1456, 1463 i innych. Jak zwykle nad Zbruczem wiele miejscowości, w tym i Nowosiółka były często zasiedlone "od nowa". Osiedla Kresów były często narażone na pełne wyludnienie. Wojny tatarsko-tureckie, włoskie, kozackie, hajdamackie i różnego rodzaju watach rabusiów niszczyły wszystko i wszystkich. Takim też kolejom losów podlegała i Nowosiółka.
W okresie międzywojennym wieś zamieszkiwało około 2000 osób. Polacy stanowili około 70% mieszkańców. Do parafii rzymsko-katolickiej, mieszczącej się w Nowosiółce Biskupiej należało wg biskupa Wincentego Urbana (z archid. lwowskiej) 808 wiernych.
W czasie wojny Ukraińcy oskarżyli ks. Jana Bojarczuka , administratora kościoła w Nowosiółce Biskupiej, o porozumiewanie się i udzielanie pomocy robotnikom rosyjskim wywożonym na przymusowe roboty. Niemcy aresztowali księdza. Siedział w więzieniu w Kamieńcu Podolskim i tam został rozstrzelany w 1941 roku.
W 1944 roku Polacy zostali ostrzeżeni, że na wieś ma nastąpić napad banderowców. Większość Polaków opuściło swoje domostwa i przeniosło się do Kamieńca Podolskiego. Ci, którzy pozostali na miejscu zostali wymordowani. Wszystkie domostwa obrabowano. Nazwisko pomordowanych nie ustalono. Zginęło wtedy około 30 osób. Znany jest też los nauczyciela z Nowosiółek Bisk. Złapany przez banderowców, związany był drutem kolczastym i wrzucony do Zbrucza. Zginął.
Wielu mieszkańców wsi złożyło ofiarę swego życia na frontach.
Zginęli na froncie:
Barylak Kazimierz s. Andrzeja, ur. 1910 Nowosiółka, kan. 63 pappanc., poległ 27.04.1945 r.
Barayło Czesław s. Franciszka, ur. 1922 Nowosiółka, szer. 2 pp, poległ 26.08.1944 r. w rej. Góry Kalwaria.
Baryło Józef s. Leopolda, ur. 1917 r., st. szer. 33 pp, poległ 19.04.1945 r. pod m. Rothenburg.
Dawydowicz Jan s. Wincentego, ur. 1914 Nowosiółka, szer. 4 zpp, zmarł 21.02.1945 r. w szpitalu ewakuacyjnym Nr 3299 w Białymstoku.
Dżus Jan s. Wasyla, ur. 1919 Nowosiółka, szer. 1 pp, zaginął bez wieści 12.10.1943 r. pod Trygubową.
Gajewski Stanisław s. Piotra, ur. 1912 Nowosiółka, plut. 4 pp, poległ 19.02.1945 r. w Będlinie.
Gułaj Stanisław s. Józefa, ur. 1925 Nowosiółka, oficer bez stopnia, ofic. pol.-wych. 29 pp, poległ 1.05.1945 r. w Droben.
Kramicz Konstanty s. Stefana, ur. 1925 Nowosiółka (?), szer. 26 pp, poległ 26.04.1945 r. pod Holschdubrau.
Naryniecki Jan s. Władysława, ur. 1912 Nowosiółka, st. szer. 5 pp, zaginął bez wieści 12.02.1945 r. w Borujsku.
Parniak Michał s. Feliksa, ur. 1901 Nowosiółka, szer. 12 pp, poległ 29.04.1945 r. pod Bradikow.
Parniak Piotr s. Józefa, ur. 1910 Nowosiółka, szer. 12 pp, poległ 6.02.1945 pod Zdbicami.
Sładnik Mikołaj s. Mikołaja, ur. 1925 Nowosiółka, szer. 11 pp, poległ 17.03.1945 r. w Kołobrzegu.
Sprugiasz Jan s. Justyna, ur. 1912 Nowosiółka, uł. 3 puł., zaginął bez wieści 19.02.1945 r.
Stempel Marian s. Franciszka, ur. 1893 Nowosiółka, szer. 14 bsap., zaginął bez wieści w 1945 r.
Urbanowski Michał s. Jana, 1906 Nowosiółka, szer. 12 pp, zaginął bez wieści 6.02.1945 r. nad jeziorem Dobre.
Urbański Jan s. Dominika, ur. 1904 Nowosiółka, szer. 14 bsap., zaginął bez wieści w 1945 r.
Waker Piotr s. Karola, ur. 1913 Nowosiółka, szer. 1 kk, poległ 28.10.1944 r.
Bibliografia
Wieś Kresowa. Czabarówka i sąsiedzi, t. 3.