Istniała tutaj już w czasach łemkowskich. Wiadomo, że działkę na nią zakupiono w 1909 r., ale działała wcześniej, skoro z archiwalnej tzw. metryki szkolnej wynika, że w roku szkolnym 1896/97 funkcjonowała jako 6-letnia Powszechna Szkoła Publiczna. Do 1919 r. dokumentacja prowadzona była w języku rusińskim (dialekt ukraińskiego).
Dowiadujemy się tego z pracy licencjackiej Lucyny Poręby streszczonej na szkolnej stronie internetowej. Z kolei założona w 1956 r. i prowadzona początkowo przez kierownika Stanisława Michalika „Kronika szkoły” podaje, że „nauka odbywała się tu w języku tubylców”, choć w okresie międzywojennym także na terenie Łemkowszczyzny nauczanie przebiegało przecież w j. polskim, a język autochtonów traktowany był tylko jako jeden z przedmiotów.
Na miejscowym cmentarzu łemkowskim najbardziej zadbaną mogiłą jest ta Feli z Dzidzinowiczów Łuckiej (ur. 8 sierpnia 1886 r., zm. 24 listopada 1916 r.), o której podano „narodna uczitelka”, co w jakimś stopniu tłumaczy troskę, z jaką był zapewne pielęgnowany jej grób, który przetrwał w niezłym stanie. Nie nażyła się długo, ledwie 30 lat – taki często był los nauczycieli, marniejących przeważnie na suchoty (gruźlicę).
Po wojnie dzieci uczyły się w pozostawionym przez Łemków parterowym, ale murowanym budynku z dwiema salami lekcyjnymi i mieszkaniem kierownika, a ponieważ był ciągle za mały – także w izbach u Jędrusika, Ptaszkowskiego i sołtysa Stanisława Siedlika. Gdy ten ostatni wyjechał na Ziemie Odzyskane, na obiekt szkolny przeznaczono cały jego dom. Potem jeszcze kierownik szkoły musiał udostępnić jedną izbę ze swego mieszkania służbowego.
Pierwszą nauczycielką po wojnie była Maria Mordarska, a mieszkania nauczycielskie urządzono w wyremontowanym domu połemkowskim. W latach 1956-58 murowaną szkołę podwyższono o drewniane piętro, mieszczące 4 sale lekcyjne, kancelarię i dwa mieszkania nauczycielskie. Do rozbudowy użyto materiału pochodzącego z rozbiórki cerkwi prawosławnej.
Od 1970 r. w szkole funkcjonowało wakacyjne schronisko turystyczne. W 1972 r. zamknięte dwa lata wcześniej przedszkole przekształcono w kolejne mieszkania dla nauczycieli oraz wygospodarowano tam dodatkową salę lekcyjną. W latach 70. placówka w Królowej G. miała filię w Boguszy, która usamodzielniła się w latach 80., jednak tylko w wydaniu 4-klasowym, bo uczniowie klas wyższych nadal uczęszczali do szkoły zbiorczej w Królowej G., tak jak teraz do miejscowego gimnazjum.
W 1982 r. za dyrektorki Marii Wacławiak zapadła decyzja o rozbudowie szkoły. Na ten czas naukę przeniesiono do domu nauczyciela, a także domów prywatnych Mariana Kościółka oraz Stanisławów Rymanowicza i Stelmacha. Trwał jednak stan wojenny, a władza w ramach oszczędności zakazała inwestycji w oświacie. Rozbudowę rozpoczęto zatem z użyciem fortelu – pod płaszczykiem remontu kapitalnego. W „Kronice…” co rusz pojawiają się uwagi o „żółwim tempie” i „przestojach w pracy”. Po dwóch latach inspektor nadzoru budowlanego kazał wszystko rozebrać.
W połowie lat 80. budowa rozpoczęła się od nowa. Przewodniczącym komitetu rozbudowy został Ryszard Gonczowski, mąż obecnej wicedyrektorki szkoły Doroty Juszczak-Gonczowskiej, a wtedy lokalny działacz ZSL, który miał poparcie absolwenta i byłego nauczyciela miejscowej szkoły Edwarda Nowaka, wtedy już prominentnego ZSL-owca z ówcześnie wojewódzkiego Nowego Sącza, którego już wymienialiśmy w części poświęconej okresowi łemkowskiemu w dziejach wsi jako współautora tendencyjnej „Monografii wsi Królowa Górna” z 1970 r.
To w tym okresie patronat nad szkołą objęły Zakłady Mechaniczne z Tarnowa, które chciały uczynić z niej swój obiekt kolonijno-wypoczynkowy. Za pieniądze tarnowskich zakładów budowa szkoły rozszerzona już o salę gimnastyczną ruszyła z kopyta.
Mało kto wiedział, że pod przykrywką niewinnej nazwy Zakłady Mechaniczne funkcjonowały zakłady zbrojeniowe. Akurat wybuchła pierwsza wojna w Zatoce Perskiej. Ponieważ koalicja antyiracka objęła dostawy broni dla Iraku embargiem, tarnowski producent uzbrojenia stanął w obliczu kryzysu. Z powodu oszczędności porzucił zatem swój niedoszły obiekt, zostawiając go w stanie rozbabranym. Ponieważ pieniądze pochodziły z funduszu socjalnego, tarnowianie zażądali zwrotu zainwestowanych środków, a było tego 4 mld zł na stare pieniądze. Potem złotówki się zdewaluowały i odstąpili od roszczeń, a inwestycję w Królowej Górnej sami nazwali „pomnikiem swojej głupoty”.
Salę gimnastyczną (pierwszą pełnowymiarową w gminie) dokończyła władza terenowa dopiero w 1996 r., a pozostawione w stanie surowym i oddane w 2001 r. nowe skrzydło przydało się na gimnazjum. W 2011 r. powstał Orlika.
Od 1988 r. Szkoła Podstawowa nosi imię Wincentego Witosa. Wymyślili to wspomniani działacze ZSL Nowak i Gonczowski. Równocześnie ufundowali sztandar. Dokręcany na drzewcu orzeł z czasem dorobił się korony.
Zespół Szkół Podstawowo-Gimnazjalnych utworzono w 2002 r. ze SzP im. Witosa i Gimnazjum, a w 2009 r. dodano Punkt Przedszkolny. Od czasu placówki prowadzonej przez KGW (w latach 1985-93 jego dyrektorką była Maria Buczek) przedszkola w Królowej Górnej bowiem nie było przez ok. 15 lat. Nowoczesny plac zabaw i bezpieczna sala zabaw powstały w ramach rządowego programu Radosna Szkoła dla uczniów klas 0-III.
Uczniowie podstawówki rekrutują się głównie z Królowej G., tylko pojedynczy z Cieniawy i Mszalnicy, zaś gimnazjum – z Królowych G. i Polskiej, Boguszy i Mszalnicy Zagóry. Uruchomiona w 2000 r. stołówka była pierwszą szkolną w gminie.
Wybitniejszym absolwentem szkoły jest boguszanin Kazimierz Kruczek, który na początku lat 90. w stopniu majora pracował w polskim ataszacie wojskowym w USA. Z kolei brat zakonny ze zgromadzenia klaretynów Jan Mężyk (absolwent z 1980 r.) był misjonarzem w Wybrzeżu Kości Słoniowej. Podarował szkole mozaiki przywiezione z Afryki.
Dyrektor Stanisław Poręba, jak i kilku innych nauczycieli sami ukończyli szkołę, w której teraz uczą.
