Dějiny školy sahají až do 19. století (konkrétně k 25.1.1885, kdy byla v Nové Pace zřízena Průmyslová škola pokračovací, která připravovala mimo jiné i pekaře, krejčí a truhláře.
Novodobé dějiny školy začínají v roce 1951, kdy dne 4. 11. 1951 vzniklo samostatné učňovské středisko cukrářské v Rokycanově ulici. V roce 1957 vznikla v budově bývalého ONV Učňovská škola, předchůdkyně dnešní SŠGS Nová Paka. Postupně začala v teoretické přípravě připravovat žáky v kovooborech, oborech cukrář, tkadlena a přadlena. Ve školním roce 1959/60 už škola disponovala celkem 17 třídami. V září 1962 byla rovněž definitivně adaptována budova ONV pro potřeby školy. Od 1. 9. 1966 jsou na škole zavedeny nové učební obory - pánská a dámská krejčí. V následujících letech se počet žáků školy pohyboval trvale v rozmezí 450-550 žáků, kteří se připravovali celkem v 6 učebních oborech.
Ve školním roce 1978/79 byl ke škole připojen učební obor pečivář ze střediska v Lomnici nad Popelkou, lomnické středisko zůstalo elokovaným pracovištěm novopacké školy až do počátku 90. let. V roce 1991 škola otevřela nový studijní obor - rodinná škola. K další významné změně došlo v roce 1996, kdy spojením středního odborného učiliště a rodinné školy byla vytvořena Integrovaná střední škola Nová Paka. Sdružovala celkem 11 oborů, z toho 4 studijní. V roce 1998 k ISŠ přibylo další zařízení - učiliště, zaměřené na 2 leté učební obory. Rozhodnutím MŠMT Praha byly v 2. polovině 90. let s okamžitou platností zrušeny rodinné školy, a proto došlo od 1. 9. 2000 ke změně názvu školy na Střední odborné učiliště a Učiliště Nová Paka. SOUaU zajišťovalo přípravu pro 19 oborů, z toho 15 učebních a 4 studijní obory. Po zrušení 2 letých oborů se škola na veřejnosti prezentovala pod názvem Střední odborné učiliště Nová Paka (od ledna do září 2006). V pořadí poslední změnou od 1. 9. 2006 se stala transformace školy ve Střední školu gastronomie a služeb Nová Paka a zavedení 4 letého oboru vzdělání s maturitní zkouškou Hotelnictví (ŠVP Hotelnictví a turismus). Od 1. 9. 2008 zahájila škola počínaje 1. ročníky přípravu podle školních vzdělávacích programů.
V současném období škola nabízí 6 oborů vzdělání s výučním listem (Cukrář, Pekař, Kuchař-číšník, Výrobce potravin – Sladovník pivovarník, Krejčí a Truhlář) a 1 obor vzdělání s maturitní zkouškou (Hotelnictví) a od 1. 9. 2023 ještě nástavbový obor s maturitní zkouškou Podnikání. Celkový počet žáků pro školní rok 2022/2023 činí 431 žáků denního studia.
Od roku 2008 se škola úspěšně zapojuje do účasti na světových soutěžích cukrářů a kuchařů (Světová olympiáda kuchařů a cukrářů a Světový pohár kuchařů a cukrářů), kde dosud získala 22 medailí (9 zlatých, 6 stříbrných a 7 bronzových).
3x 
5x 