1865. gadā Zaļmuižas pagastā Miglinieku sādžā tika atvērta pirmā skola. 1866. gadā skolā mācījās 14 zēni un strādāja viens skolotājs, 1873.gadā mācījās 32 zēni un 3 meitenes. 1880. gados skolu pārcēla uz Zaļmuižu., bet 20. gadsimta sākumā uz Rogovku. Skolā mācības notika krievu valodā. 1911. gadā skolu apmeklēja 135 bērni.

1914. gadā uzcēla jauno skolas ēku. Kopš 1919. g. mācības skolā notika latviešu valodā. 1920. gadu sākumā skolu pārveidoja par 6-klasīgo pamatskolu. 1926. gadā Rogovkas 6-klasīgo pamatskolu apmeklēja 142 skolēni un strādāja 3 skolotāji.

1936. gada 26. februārī Rogovkas sešklasīgā pamatskola pārdēvēta par Nautrēnu sešklasīgo pamatskolu.

1935. gadā tika lemts būvēt jaunu skolas ēku, būvprojektu izstrādāja arhitekts P.Pavlovs, 1937. gadā 5.jūnijā skolai tika likts pamatakmens un iemūrēta kapsula ar novēlējumu nākamajām paaudzēm. Jaunā skolas ēka tika iesvētīta 1938. gadā 2. oktobrī. Iesvētīšanu vadīja draudzes dekāns J.Deksnis un izglītības ministra biedrs J.Čamanis.

Par pārziņiem strādāja Aloizs Gudrītis, Pēteris Ūbelītis, Edgars Treimanis, Jānis Ruško, Jānis Ludboržs (Madsolas Jōņs),

1945. gadā tika pieņemts likums par vidusskolas atvēršanu Nautrēnos. 1947. gadā skolā strādāja 24 skolotāji, 1949. gadā 41 skolotājs.

1967. gadā tika uzcelta piebūve ar sešām klašu telpām un sporta zāli. 1974. gadā pie skolas tika uzcelts internāts. 1946. gadā skolā mācījās 374 (vidusskolā – 87) skolēni, strādāja 24 skolotāji, 1950. gadā – 388 (102), 40 skolotāji, 1970. gadā – 314 (46), 26 skolotāji, 1989. gadā – 194(42), 23 skolotāji.

Skolas direktori – J.Gailāns. K.Krigers, A.Ansviesulis, A.Laurāne, I.Rudze, A.Barkāne, F.Sjomkāne, V.Katkeviča. No 1971. gada skolas direktori – E.Barkāne, A.Miglinieks, A.Žogota.

1999. gada 1. septembrī Nautrēnu pagastu iekļāva Rēzeknes rajonā (2009. gadā – Rēzeknes novadā).