Podlaski Oddział Straży Granicznej zastąpił rozformowaną Podlasko-Mazurską Brygadę Wojsk Ochrony Pogranicza. Zasięg terytorialny i struktura komendy zostały określone przez Komendanta Głównego Straży Granicznej w zarządzeniu nr 6/91 z 14 lutego 1991 r. Pierwszym komendantem Podlaskiego Oddziału Straży Granicznej został płk Zdzisław Jakubiszyn.
Oddziałowi powierzono do ochrony granicę o długości 351 km, rozciągającą się od Bugu, aż po trójstyk rubieży Polski, Litwy i Rosji (obwodu kaliningradzkiego). Blisko 105 km tego odcinka stanowiła granica polsko-litewska, a prawie 245 km granica polsko-białoruska.
Zasięg działania oddziału przekładał się na województwa: białostockie i suwalskie. W skład Podlaskiego Oddziału Straży Granicznej w 1991 r. wchodziło siedem strażnic, pięć granicznych placówek kontrolnych oraz pięć kompanii odwodowych. Siedzibę komendy oddziału ustanowiono w koszarach Wojsk Ochrony Pogranicza przy ul. Bema 100 w Białymstoku.
20 stycznia 1992 r. ówczesny Komendant Główny Straży Granicznej płk Marek Lisiecki nadał Podlaskiemu Oddziałowi Straży Granicznej sztandar oraz imię generała dywizji Henryka Minkiewicza.
Dużym wyzwaniem dla Podlaskiego Oddziału Straży Granicznej we wczesnych latach 90-tych była rozbudowa infrastruktury granicznej, będącej w stanie obsłużyć stale zwiększający się ruch. Uruchomiono wtedy przejścia graniczne w Budzisku i w Bobrownikach. Jednocześnie, proporcjonalnie do wzrostu przestępczości zorganizowanej i przemytu międzynarodowego, uszczelniano granicę wschodnią. Rozpoczął się więc również proces powiększania sieci strażnic: w latach dziewięćdziesiątych w Podlaskim Oddziale Straży Granicznej otwarto strażnice w Szypliszkach, Wiżajnach, Krynkach, Mielniku i Nowym Dworze.
Od sierpnia 1993 r. na odcinku oddziału zaczęły masowo pojawiać się nielegalne przeloty statków powietrznych na niewielkich wysokościach, z Litwy do Polski. Aby temu przeciwdziałać, w Podlaskim Oddziale Straży Granicznej zaczęła działać oddelegowana z Jednostek Nadwiślańskich WP grupa lotnicza. W roku 1996 zaś powołano Wydział Lotniczy.
Stopniowo wprowadzano kolejne zmiany w strukturach organizacyjnych, uzupełniano również wyposażenie i wprowadzano kolejne metody: w 1999 r. do patrolowania trudnych odcinków (w Wiżajnach i Białowieży) wykorzystywano konie wierzchowe; po kilku latach zrezygnowano jednak z tego pomysłu.
Podlaski Oddział Straży Granicznej został również odmłodzony kadrowo. W 1996 r. rozpoczęto uzawodowienie Straży Granicznej: do służby w Podlaskim Oddziale Straży Granicznej przyjęto wówczas aż 94 funkcjonariuszy służby przygotowawczej. Dekadę później, w połowie 2006 r. zwolnieni zostali do rezerwy ostatni funkcjonariusze służby kandydackiej.
Lata 90-te zapisały się również jako czas przygotowań do wejścia Polski do Unii Europejskiej. W Podlaskim Oddziale Straży Granicznej oprócz wprowadzanych centralnie zmian prawnych i technicznych, wynikających m.in. z konieczności standaryzacji i kompatybilności sprzętu stosowanego w ochronie granicy, odnotowano wiele wizyt delegacji zagranicznych, sprawdzających stan przygotowania Straży Granicznej oraz wykorzystywanie funduszu PHARE.
Rozwijała się również współpraca instytucjonalna, także międzynarodowa. Aby usprawnić wymianę informacji pomiędzy państwami, w 2002 r. w Budzisku został otwarty Punkt Kontaktowy Straży Granicznej RP i Służby Ochrony Granicy Państwowej przy Ministerstwie Spraw Wewnętrznych RL Budzisko-Kalwaria.
Na przestrzeni lat przeprowadzano kolejne zmiany organizacyjne, np. włączono do systemu ochrony granicy jednostki w Puńsku (2000 r.), Płaskiej, Narewce (2001 r.), Dubiczach Cerkiewnych i Michałowie (2002 r.). Niektóre strażnice znoszono: w roku 2002 rozwiązane zostały strażnice w Szypliszkach, Sejnach, Sokółce, Gródku i Czeremsze. Ich zadania przejęły graniczne placówki kontrolne w Budzisku, Ogrodnikach, Kuźnicy, Bobrownikach i Czeremsze. W 2004 roku zakończyła działalność strażnica w Puńsku.
1 maja 2004 r. Polska weszła do Unii Europejskiej. W Podlaskim Oddziale Straży Granicznej działało wówczas 18 granicznych jednostek organizacyjnych: w Wiżajnach, Rutce Tartak, Płaskiej, Lipsku, Nowym Dworze, Szudziałowie, Krynkach, Michałowie, Białowieży, Dubiczach Cerkiewnych, Mielniku, Budzisku, Ogrodnikach, Kuźnicy, Bobrownikach, Siemianówce, Czeremsze oraz Samodzielna Kompania Odwodowa w Suwałkach.
W 2005 r. otwarto osobowe przejście graniczne Białowieża – Piererow oraz przejście rzeczne na Kanale Augustowskim – Rudawka-Lesnaja. Rok później uruchomiono przejście Berżniki – Kapciamiestis, które przestało działać z momentem akcesji Polski do Schengen w 2007 r.
Wejście do strefy Schengen było ostatnim etapem pełnej integracji z Unią Europejską. Jednym z warunków akcesji było dostosowanie istniejących w Straży Granicznej procedur administracyjnych, infrastruktury oraz stanu prawnego do wymogów schengeńskich. Postępy w tej dziedzinie oceniali unijni eksperci w ramach misji ewaluacyjnych. W Podlaskim Oddziale Straży Granicznej odbyły się dwie takie kontrole: w roku 2006 i 2007.
W 2009 r. utworzono placówkę SG w Augustowie, otwarto również nowe obiekty w Czeremsze i Mielniku.
Jako najtragiczniejszy dzień w historii oddziału zapisał się 31 października 2009 r. – dzień katastrofy śmigłowca SG. W katastrofie zginęli por. SG Andrzej Żukowski, chor. szt. SG Bartłomiej Bartnicki i chor. SG Marcin Bezubik. Rok później, na miejscu wypadku został odsłonięty pomnik ufundowany z dobrowolnych składek oficerów Państwowego Komitetu Granicznego Republiki Białoruś.
W XXI rocznicę powołania Straży Granicznej, 22 maja 2012 r., Podlaski Oddział Straży Granicznej otrzymał nowy sztandar. 16 i 17 maja 2013 r. w Białymstoku odbywały się centralne uroczystości związane ze świętem Straży Granicznej.
Komendanci Podlaskiego Oddziału Straży Granicznej:
- 16.02.1991 - 31.07.1993 - płk Zdzisław Jakubiszyn
- 01.08.1993 - 24.09.1997 - płk SG Leszek Czech
- 25.09.1997 - 15.12.1997 - ppłk SG Stanisław Mika
- 16.12.1997 - 31.01.2002 - płk SG Leszek Czech
- 01.02.2002 - 26.09.2005 - gen. bryg. SG Włodzimierz Gryc
- 27.09.2005 - 02.05.2009 - płk SG Marian Pogoda
- 03.05.2009 - 03.11.2013 - płk SG Leszek Czech
- 04.11.2013 - 16.06.2016 - płk SG Andrzej Rytwiński
- 17.06.2016 - 06.07.2021 - gen. bryg. SG Grzegorz Biziuk
- 07.07.2021 - 21.02.2024 - gen.bryg. SG Andrzej Jakubaszek
- 22.02.2024 - obecnie - płk SG Sławomir Klekotka