Archiwum powstało w 1950 r. jako Oddział Powiatowy w Nowym Sączu Wojewódzkiego Archiwum Państwowego w Krakowie. Następnie na podstawie dekretu z 29.03.1951 r. działało jako Powiatowe Archiwum Państwowe. Od 1958 r. znów działało jako Oddział Terenowy Archiwum Państwowego Miasta Krakowa i Województwa Krakowskiego.

Początkowo Archiwum obejmowało zasięgiem działania powiaty: nowosądecki, limanowski, nowotarski i gorlicki, a od 1955 r, po utworzeniu w 1952 r. Powiatowego Archiwum Państwowego w Nowym Targu, jedynie powiaty nowosądecki i limanowski. Po reformie administracyjnej w 1976 r. powstało Wojewódzkie Archiwum Państwowe w Nowym Sączu z siedzibą w Nowym Targu, które zostało zlikwidowane w 1982 r. Wówczas Archiwum znów zostało oddziałem zamiejscowym Archiwum Państwowego w Krakowie i odtąd obejmowało zasięgiem powiaty: nowosądecki, gorlicki i wschodnią część limanowskiego.

Po likwidacji oddziału w Nowym Targu w 2010 r. jego zasób archiwalny został podporządkowany ewidencyjnie Oddziałowi w Nowym Sączu (do 2015 r. zasób nowotarski przyporządkowany został Oddziałowi III ANK). Od początku Oddział boryka się z problemami lokalowymi i był często przenoszony. Pierwsza siedziba Oddziału (1950-1975) znajdowała się przy ul. Pijarskiej 3 (obecnie siedziba Sądu Okręgowego w Nowym Sączu). W kolejnych latach następowało jeszcze kilka przenosin. W latach 2003-2019 siedzibą był budynek przy ul. Jagiellońskiej 56a, w dawnym budynku banku NBP, który Prezydent Miasta przekazał Prokuraturze Okręgowej w Nowym Sączu z zastrzeżeniem zabezpieczenia potrzeb Oddziału Archiwum. Po wypowiedzeniu tej siedziby przez prokuraturę, Archiwum ma od 2019 r. siedzibę przy ul. Jagiellońskiej 54. Równocześnie rozpoczęły się działania w kierunku budowy nowej siedziby dla Oddziału w Nowym Sączu.

Zasób Archiwum Narodowego w Krakowie Oddział w Nowym Sączu, w zwartej części sięga końca XVIII wieku. Pojedyncze księgi powstały w okresie staropolskim, a najstarsza z nich pochodzi z XV wieku. Są to zarówno akta instytucji państwowych i samorządowych, przedsiębiorstw i stowarzyszeń, jak też archiwalia zgromadzone w zbiorach specjalnych, np. Sandecjana, Zbiór Fotograficzny. Szczególnie dobrze zachowane są akta miast Nowego i Starego Sącza od czasów zaborów. Wcześniejsze archiwalia zostały znacznie uszczuplone. Podczas pożaru ratusza w Nowym Sączu w 1894 r. spłonęły wraz z nim bezcenne pergaminowe dokumenty nowosądeckie – przywileje królewskie w liczbie ok. 300 dokumentów. Ocalałe księgi radzieckie i ławnicze oddano w depozyt do Archiwum Akt Dawnych Miasta Krakowa (przechowywane do dziś w Archiwum Narodowym w Krakowie).   To co zostało w Nowym Sączu, zaginęło podczas II wojny światowej. W 1944 r. Niemcy wywieźli księgi wójtowsko-ławnicze i przywileje pergaminowe starosądeckie oraz księgi cechowe, sądowe nowosądeckie, akta kameralne i pewna ilość archiwaliów ściągniętych podczas okupacji do Nowego Sącza z okolicznych miejscowości (z Limanowej, Grybowa, Muszyny, i innych). Podjęte po wojnie poszukiwania tych akt i dokumentów nie przyniosły skutku.