W roku 1944 powstało Nadleśnictwo Olszyny z siedzibą w Kołaczycach (w domu prywatnym), a jego pierwszym Nadleśniczym był Arłamowski (nie znamy jego imienia). Administracyjnie Nadleśnictwo podlegało pod Zarząd Lasów Państwowych w Rzeszowie z siedzibą w Tarnowie. Wówczas powierzchnia Nadleśnictwa Olszyny wynosiła ok. 4,5 tys. ha, a jego terytorium obejmowało pięć leśnictw: Bieździedza, Jodłowa, Lipnica, Brzostek oraz Kamienica Dolna. Każde leśnictwo dzieliło się na obchody o powierzchni ok. 300 ha. Po Nadleśniczym Arłamowskim władzę w Nadleśnictwie Olszyny na krótko objął Nadleśniczy Wysocki (jednak daty nie są znane, wiadomo tylko, że zamieszkiwał dworek w Bieździedzy). W roku 1946 nastąpiła zmiana nazwy Nadleśnictwa Olszyny na Nadleśnictwo Kołaczyce. Dodatkowo zmieniono nazwę leśnictwo Jodłowa na leśnictwo Czermna. Przed rokiem 1950 Nadleśniczym został Juliusz Misiołek, a Nadleśnictwo funkcjonowało w oparciu o trzy stanowiska: nadleśniczego, kierownika biura i manipulanta (dzisiejszy stażysta). W październiku 1951 r. siedzibę Okręgowego Zarządu Lasów Państwowych przeniesiono z Tarnowa do Przemyśla. Pięć lat później (1956r.) po Juliuszu Misiołku władzę w Nadleśnictwie Kołaczyce objął Kazimierz Malawski, przechodząc z Nadleśnictwa Krasiczyn (posiadał on wyższe wykształcenie leśne).

Lata 70. przyniosły wiele zmian, zarówno na płaszczyźnie administracyjnej, jak i terytorialnej.  Do tej pory w biurach nadleśnictw były zatrudnione ok. 3-4 osoby, a pionem decyzyjnym były wyłącznie jednostki nadrzędne. Dopiero wprowadzone zmiany w strukturze nadleśnictw spowodowały powstanie działu technicznego. W roku 1972 siedzibę Nadleśnictwa przeniesiono z Kołaczyc do Nawsia Kołaczyckiego. Została ona wybudowana na podstawie tradycyjnych projektów, które obowiązywały wówczas dla siedzib nadleśnictw w Lasach Państwowych. Aktualnie w tym budynku mieści się kancelaria leśnictwa Bieździedza, archiwum oraz pokoje gościnne.

W wyniku reorganizacji terytorialnej doszło do łączenia nadleśnictw. Od tej pory powierzchnia  każdego z nich liczyła od 8 do 15 tys. ha. Również zasięg naszej jednostki uległ zmianie. Do Nadleśnictwa Kołaczyce przyłączono cztery leśnictwa: Pagorzynę, Tarnowiec, Bierówkę i Pietruszą Wolę, a odłączono leśnictwa: Brzostek i Kamienicę Dolną.

Duża zmiana nastąpiła w lipcu 1975 r., kiedy to OZLP Przemyśl połączono z OZLP  Kraków w jedno przedsiębiorstwo z siedzibą w Krakowie. Dwa lata później, w  roku 1977 do terytorium Nadleśnictwa Kołaczyce została włączona część uprzednio istniejących Nadleśnictw: Gorlice, Wiśniowa i Nowy Żmigród. Rok późnej w 1978 r. Okręgowy Zarząd Lasów Państwowych został ponownie przeniesiony, tym razem z Krakowa do Krosna.

W roku 1986 na stanowisko Nadleśniczego został powołany Andrzej Kulczycki i tak było do roku 1991, kiedy to jego następcą został Leszek Nalepa. W ciągu następnych lat zaplanowano budowę nowej siedziby Nadleśnictwa, naprzeciwko starej, i tak w listopadzie 1988 r. wydano decyzję o warunkach zabudowy i zagospodarowania terenu. W lipcu 2000 r. podpisano protokół odbioru nowej siedziby, a po ponad pół roku we wrześniu 2001 r. nastąpiło uroczyste otwarcie budynku biura.

Końcem kwietnia 2004 r. ówczesny Nadleśniczy Leszek Nalepa został odwołany z Kołaczyc i powołany na to samo stanowisko w Nadleśnictwie Dukla. W tym samym czasie w Nadleśnictwie Kołaczyce obowiązki Nadleśniczego zaczął pełnić dotychczasowy zastępca Jerzy Iwański i tak pozostało do końca 2004 r. Dzień 31 grudnia 2004 przyniósł wiele zmian, bowiem Nadleśnictwo Kołaczyce zostało rozwiązane, a wszyscy pracownicy przeniesieni do Nadleśnictwa Dukla. W roku 2007 po śmierci Nadleśniczego Leszka Nalepy na to stanowisko został powołany Andrzej Kochmański. Przełomowy był rok 2008, bowiem z dniem 1 stycznia Nadleśnictwo Kołaczyce zostało przywrócone z jego wcześniejszą siedzibą w Nawsiu Kołaczyckim.

Od tego momentu Nadleśnictwo Kołaczyce miało dwa obręby: Kołaczyce i Krosno (przyłączony z Nadleśnictwa Dukla). Na stanowisko Nadleśniczego został powołany Jan Kraczek, ale na krótko, bo tylko na 6 dni. Po jednodniowej przerwie w dniu 9 stycznia obowiązki Nadleśniczego zaczął pełnić dotychczasowy zastępca Ireneusz Hołodniak i trwało to do 28 stycznia. W dniu 29 stycznia został powołany nowy Nadleśniczy Andrzej Kochmański, który zarządzał Nadleśnictwem przez ponad 8 lat - do 8 czerwca 2016r. W tym samym dniu kierownictwo nad Nadleśnictwem objął Artur Paczkowski.

Aktualnie Nadleśnictwo Kołaczyce obejmuje powierzchnię 10 700,98 ha i podzielone jest na dwa obręby leśne: Kołaczyce - obejmujący 6 leśnictw (Bierówka, Bieździedza, Lisów, Pagorzyna, Pietrusza Wola, Tarnowiec) i Krosno - obejmujący 4 leśnictwa (Czarnorzeki, Węglówka, Odrzykoń i Wola Komborska).