Teren zarządzany przez Nadleśnictwo Myszyniec zajmowała w przeszłości Puszcza Zielona. Od średniowiecza obszary te stanowiły własność książat mazowieckich, później przeszły w posiadanie królów polskich, a następnie zaborców. W wiekach XVI–XIX ze wzrostem populacji oraz intensywną eksploatacją lasu obszar kniei zmniejszał się. Niekontrolowana wycinka drzew w XIX wieku spowodowała pokaźne szkody w Puszczy Zielonej[1].
Nadleśnictwo Myszyniec w swoim pierwotnym kształcie powstało prawdopodobnie w 1887[2]. W 1907 istniała jednostka określana jako Leśnictwo Myszyniec. W 1918 przemianowano je na Nadleśnictwo Myszyniec[3]. W 1928 z części Nadleśnictw Myszyniec i Ostrołęka stworzono Nadleśnictwo Podgórze. Od 1959 nadleśnictwo podlegało pod Rejon Lasów Państwowych w Ostrołęce. W tym samym roku, po likwidacji rejonów, nadleśnictwo zaczęło podlegać bezpośrednio Zarządowi Lasów Państwowych w Siedlcach[4]. W 1973 do nadleśnictwa dołączono Nadleśnictwo Podgórze[3]. W 1975 wcielono je do Okręgowego Zarządu Lasów Państwowych w Olsztynie (przekształcony w Regionalną Dyrekcję Lasów Państwowych w Olsztynie)[1]. W 1978 do nadleśnictwa włączono część dawnego obrębu Lipniki, dotąd znajdującego się w Nadleśnictwie Nowogród[3].