Historia naszego Oddziału rozpoczęła się 30 kwietnia 1991roku, kiedy to Komendant Główny Straży Granicznej na podstawie art. 6 w związku z art. 5 ust. 1 i 5 ustawy z dnia 12 października 1990 roku o Straży Granicznej zarządzeniem nr 019/Org. polecił zorganizować Oddział Straży Granicznej w Chełmie. Powierzył NOSG do ochrony odcinek granicy państwowej od znaku granicznego nr 677 włącznie do znaku granicznego nr 1346 włącznie o długości 457 km 640 m.
Organizacja Straży Granicznej została zakończona przed ustawowo określonym terminem. Zgodnie z zarządzeniem numer 47/91 Ministra Spraw Wewnętrznych Henryka Majewskiego z dniem 15 maja 1991r. zostały rozformowane Wojska Ochrony Pogranicza, zaś od 16 maja 1991r. Straż Graniczna przejęła ochronę granicy państwowej RP i kontrolę ruchu granicznego. Dzień 16 maja został ustanowiony Dniem Straży Granicznej.
Nadbużański Oddział Straży Granicznej w Chełmie powstał w wyniku rozwiązania Nadbużańskiego Batalionu Wojsk Ochrony Pogranicza, który sformowano na bazie Nadbużańskiej Brygady WOP na podstawie rozkazu DWOP nr 03 z 31.07.1989. Podlegał on Bieszczadzkiej Brygadzie WOP w Przemyślu. Lewy odcinek Nadbużańskiej Brygady wraz ze strażnicami Janów Podlaski, Terespol i Sławatycze przekazano Mazurskiej Brygadzie WOP w Białymstoku. Brygada ta przejęła również GPK Terespol – Kukuryki. GPK Dorohusk podporządkowano Bieszczadzkiej Brygadzie WOP w Przemyślu.
W dniu 30 października 1989 roku na placu alarmowym jednostki odbyło się uroczyste pożegnanie żołnierzy ze sztandarem rozformowanej Nadbużańskiej Brygady. Dowódcą Nadbużańskiego Batalionu został płk Henryk Makowski. Pełnił tę funkcję niespełna dwa lata bowiem Nadbużański Batalion rozformowano 15 maja 1991 roku. Na jego bazie sformowano Nadbużański Oddział Straży Granicznej, który przejął odcinek i zadania związane z jego ochroną. Dnia 11 kwietnia 1991 roku ppłk dypl. Józef Biedroń został powołany pierwszym Komendantem Nadbużańskiego Oddziału Straży Granicznej.
Nadbużańskiemu Oddziałowi Straży Granicznej na podstawie decyzji Komendanta Głównego Straży Granicznej nr 1 z dnia 18 września 1991roku został nadany sztandar i imię „27 Wołyńskiej Dywizji Armii Krajowej’’. Rozpoczynając uroczystość 22 września 1991 roku w Dorohusku, Komendant Nadbużańskiego Oddziału Straży Granicznej ppłk dypl. Józef Biedroń złożył Komendantowi Głównemu Straży Granicznej meldunek o gotowości zgrupowania NOSG do uroczystości nadania sztandaru i imienia 27 Wołyńskiej Dywizji Armii Krajowej Nadbużańskiemu Oddziałowi Straży Granicznej w Chełmie.
Porucznik w st. spocz. Tadeusz Persz ps. „Głaz” sztandar przekazał Komendantowi Głównemu Straży Granicznej płk. prof. dr. hab. Markowi Lisieckiemu. Następnie sztandar ucałowany przez Komendanta Nadbużańskiego Oddziału Straży Granicznej ppłk. dypl. Józefa Biedronia stał się oficjalnym sztandarem Oddziału.
W dniu 29 września 1991 roku w Wytycznie odbyło się przekazanie Pomnika – Kopca chwały żołnierzy Korpusu Ochrony Pogranicza Straży Granicznej – sukcesorce tradycji KOP–u. Monument wzniesiony został w 1989 roku na 50–lecie bitwy pod Wytycznem. Stanowi go wysoki kopiec z metalowym krzyżem, a obok mogiły z 14 płyt z nazwiskami i dalej groby bezimienne. Spoczywają tam Ci, którzy zginęli walcząc o wolność i nienaruszalność granic.
W początkach formowania się Nadbużańskiego Oddziału SG swój znaczący wkład miało Chełmskie Środowisko Żołnierzy 27 Wołyńskiej Dywizji Piechoty Armii Krajowej. Kombatanci zapraszani są na wszelkie patriotyczne uroczystości organizowane przez Nasz Oddział. Współpraca zaowocowała odbudową cmentarza parafialnego w Zasmykach, uznanego później za cmentarz wojenny 27 WDP AK.
Bardzo ważnym momentem z życia Oddziału było wejście Polski do Unii Europejskiej oraz przystąpienie naszego kraju do Układu z Schengen. Nadbużański Oddział Straży Granicznej poprzez realizacje programu dostosowania SG do standardów Schengen przygotowywał się na przystąpienie do Układu i przejęcie obowiązku ochrony zewnętrznej granicy strefy. W ramach realizacji II etapu tego programu w dniu 15 kwietnia 2002 roku zreorganizowano Komendę Oddziału. Z kolei w ramach III etapu z dnia 15 października, pilotażowo – zreorganizowano graniczne jednostki organizacyjne SG w Terespolu. Zlikwidowano odrębną strażnicę SG i połączono ją z miejscową graniczną placówką kontrolną SG. Nowo utworzona graniczna jednostka organizacyjna pod nazwą „graniczna placówka kontrolna SG w Terespolu”. Z końcem 2002 roku został zakończony III etap reorganizacji Straży Granicznej, w ramach którego połączono wszystkie graniczne placówki kontrolne z wytypowanymi strażnicami SG. Nowo powstałe Graniczne Placówki Kontrolne przejęły zadania dotychczasowych strażnic. W związku z powyższym działalność w roku 2003 NOSG rozpoczął siłami 5 GPK i 10 strażnic.
W tym samym roku wprowadzone zostały wizy dla obywateli Rosji, Ukrainy i Białorusi. Spowodowało to drastyczny spadek w ruchu granicznym. W ciągu pierwszej doby po wprowadzeniu obowiązku wizowego z przejść granicznych obsługiwanych przez Oddział skorzystało o połowę mniej podróżnych niż w okresie ruchu bezwizowego.
Podstawę prawną do zniesienia z dniem 21 grudnia 2007 r. kontroli osób na granicach wewnętrznych lądowych i morskich, a z dniem 30 marca 2008 r. także na granicach powietrznych, stanowi Decyzja Rady z dnia 6 grudnia 2007 r.
Od momentu powstania Straży Granicznej zakres jej zadań był systematycznie rozszerzany o uprawnienia o charakterze policyjnym, związane ze zwalczaniem szeroko rozumianej przestępczości granicznej. W dniu wejścia Polski do Unii Europejskiej Nadbużański Oddział Straży Granicznej był w pełni przygotowany do podjęcia zadań w ochronie części zewnętrznych granic Unii Europejskiej oraz współpracy z formacjami granicznymi Unii Europejskiej i „Schengen”.
Nadbużański Oddział Straży Granicznej ochrania granicę państwową z Republiką Białorusi i Ukrainą o łącznej długości odcinka 467 km 570 m, w tym z Republiką Białorusi – 171 km 310 m i z Ukrainą 296 km 260 m.
Dziś Nadbużański Oddział Straży Granicznej w Chełmie to największy oddział SG w Polsce. Strzeże już nie tylko granic Rzeczpospolitej Polskiej lecz także granicy zewnętrznej Unii Europejskiej i Strefy Schengen czyli obszaru, na którym zniesiona została kontrola graniczna na granicach wewnętrznych oraz stosowane są ściśle określone jednolite zasady dotyczące kontroli na granicach zewnętrznych. Jesteśmy gwarantem bezpieczeństwa dla obywateli Unii Europejskiej przed przedostaniem się do Europy osób, których pobyt mógłby stanowić zagrożenie dla jej bezpieczeństwa i obronności. To na barkach funkcjonariuszy m.in. naszego oddziału spoczywa odpowiedzialność za przestrzeganie ładu i porządku osób przekraczających granicę. Z czasów kiedy granicę wschodnią Polski chroniono przy pomocy zasiek z drutów i prowizorycznych drewnianych wież obserwacyjnych oraz patroli wyposażonych w motory WSK dziś nie pozostało już nic. Obecny system ochrony granicy państwowej wyposażony jest w najnowsze techniki informatyczne i teleinformatyczne. Do ochrony granicy wykorzystywane są pojazdy obserwacyjne, wyposażone w nowoczesne kamery termowizyjne umożliwiające prowadzenie obserwacji nocą. Pojazdy te stanowią mobilne centra przeznaczone do patrolowania terenu, oraz wykrywania i rozpoznawania obiektów. Do patrolowania granicy państwowej używa się dzisiaj motocykli, quadów. Zimą w szczególnie trudnych warunkach terenowych Straż Graniczna pełni służbę przy pomocy nart i skuterów śnieżnych. Do patrolowania odcinka granicy wykorzystywane są również śmigłowce.
Nadbużański Oddział Straży Granicznej z chwilą utworzenia realizował zadania siłami 8 strażnic i 4 granicznych placówek kontrolnych, co powodowało, że każda strażnica średnio ochraniała około 60 km granicy. Obecnie w NOSG funkcjonuje 20 Placówek Straży Granicznej (18 pełniących służbę w bezposredniej ochronie granicy państwa oraz dwie w głebi kraju) i 12 przejść granicznych w tym 7 drogowych, 4 kolejowe i 1 lotnicze. Średnia długość ochranianego odcinka granicy państwowej przez jedną placówkę wynosi około 25 km.
Podczas obchodów Święta Straży Granicznej 18 maja 2011 roku w Chełmie na Placu Łuczkowskiego odbyła się ceremonia pożegnania sztandaru, który dotychczas reprezentował Nadbużański Oddział Straży Granicznej oraz uroczyste nadanie nowego sztandaru. Nowy sztandar został ufundowany dzięki staraniom utworzonego 17 stycznia 2011 roku Komitetu Społecznego pod przewodnictwem Prezesa Chełmskiego Środowiska 27 Wołyńskiej Dywizji Armii Krajowej. Środki na ten szczytny cel uzyskano w ramach zbiórki publicznej, w której wzięły udział instytucje państwowe oraz samorządowe, organizacje społeczne, ludność Lubelszczyzny oraz funkcjonariusze i pracownicy Nadbużańskiego Oddziału Straży Granicznej. Honorowym patronatem inicjatywę objął Wiceminister Spraw Wewnętrznych i Administracji Adam Rapacki. Pożegnania sztandaru oraz wręczenia nowego dokonał gen. bryg. SG Jarosław Frączyk – komendant NOSG.
W dniu 28 września 2012 roku, na terenie Komendy Nadbużańskiego Oddziału Straży Granicznej w Chełmie odbyła się uroczystość odsłonięcia pomnika poświęconego "Bohaterom Polskich Służb Granicznych Chroniących Granic Niepodległej Polski". Pomnik powstał z inicjatywy Straży Granicznej w pracowni rzeźbiarskiej Witolda Marcewicza w Bełżycach. Monument upamiętnia funkcjonariuszy i żołnierzy wszystkich formacji granicznych - przedwojennego Korpusu Ochrony Pogranicza, powojennych Wojsk Ochrony Pogranicza i dzisiejszej Straży Granicznej. Pomnik sfinansowano z dobrowolnych składek przy udziale Rady Ochrony Pamięci Walk i Męczeństwa oraz Związków Zawodowych. Zastąpił on pomnik poświęcony "Chwale Bohaterom WOP 1945-1991".
Płk dypl. SG Józef Biedroń w dniu 11 kwietnia 1991 roku został powołany przez Komendanta Głównego Straży Granicznej płk. prof. dr. hab. Marka Lisieckiego na pierwszego Komendanta Oddziału. W dniu 10 listopada 1994 roku ppłk dypl. Józef Biedroń otrzymał akt mianowania na wyższy stopień w Straży Granicznej – pułkownika. W dniu 7 listopada do Oddziału przybył Komendant Główny Straży Granicznej gen. bryg Marek Bieńkowski i odczytał postanowienie MSWiA o odwołaniu ze stanowiska Komendanta NOSG płk dypl. Józefa Biedronia oraz powołanie na to stanowisko mjr SG Marka Dominiaka. Płk dypl. J. Biedroń sprawował swoje obowiązki do 6 listopada 2000 roku.
Gen. bryg SG Marek Dominiak w dniu 7 listopada 2000 roku został powołany na stanowisko Komendanta Nadbużańskiego Oddziału Straży Granicznej. Pod koniec roku Komendant uczestniczył w Warszawie w przekazaniu śmigłowca Komendzie Oddziału. Jedną z ważniejszych dat podczas jego służby w Oddziale jest 1 maja 2004 roku: Polska przejęła wówczas obowiązki ochrony zewnętrznej granicy Unii Europejskiej. Rok później, 13 maja 2005 płk Marek Dominiak na podstawie postanowienia Prezydenta Rzeczypospolitej Polskiej został nominowany na stopień generała brygady. Na wniosek Komendanta Głównego Straży Granicznej gen. bryg. SG Mirosława Kuśmierczaka w dniu 25 czerwca 2007 roku gen. bryg. SG Marek Dominiak został odwołany ze stanowiska Komendanta Nadbużańskiego OSG.
Płk SG Wiesław Świętosławski został powołany na stanowisko Komendanta Nadbużańskiego Oddziału Straży Granicznej dnia 26 czerwca 2007 roku na wniosek Komendanta Głównego Straży Granicznej gen. bryg. SG Mirosława Kuśmierczaka. W tym samym roku 21–22 grudnia Polska przystąpiła do Układu Schengen i przejęła obowiązki ochrony zewnętrznej granicy strefy. Stanowisko Komendanta NOSG pełnił do dnia 2 kwietnia 2009 roku.
Płk SG Marian Pogoda na stanowisko Komendanta NOSG został powołany dnia 3 kwietnia 2009 roku. Jest absolwentem Wyższej Szkoły Oficerskiej Wojsk Zmechanizowanych we Wrocławiu. W okresie od 1994 do 1997 roku pełnił służbę w Komendzie Głównej Straży Granicznej. W latach 1997 – 2009 kontynuował służbę w Podlaskim Oddziale SG. Z dniem 1 lipca 1998 roku został powołany na stanowisko Zastępcy Komendanta Podlaskiego Oddziału, a 27 września 2005 roku na Komendanta Podlaskiego Oddziału Straży Granicznej. Z dniem 11 kwietnia 2011 Minister SWiA na wniosek Komendanta Głównego SG odwołał płk. SG Mariana Pogodę ze stanowiska Komendanta Nadbużańskiego OSG.
Gen. bryg. SG Jarosław Frączyk od 1995 do 1998 roku służbę pełnił na stanowiskach Zastępcy Komendanta Lubuskiego i Śląskiego Oddziału SG oraz na stanowiskach kierowniczych w Komendzie Głównej SG. W latach 1998 – 2006 na stanowiskach Zastępcy Komendanta Głównego Straży Granicznej, Zastępcy i Dyrektora Inspektoratu Nadzoru i Kontroli Komendanta Głównego Straży Granicznej. Od 19.04.2006 roku służbę pełnił na stanowisku Komendanta Lubuskiego Oddziału SG. Od 01.06.2009 do 11.04.2011 roku na stanowisku Komendanta Nadodrzańskiego Oddziału SG. Od 12 kwietnia 2011 roku powołany na stanowisko Komendanta Nadbużańskiego OSG. W dniu 14 maja 2011 roku płk SG Jarosław Frączyk otrzymał nominację na stopień generała brygady Straży Granicznej.
Płk SG Waldemar Skarbek na stanowisko Komendanta NOSG został powołany dnia 3 października 2014 roku przez Komendanta Głownego Straży Granicznej gen. dyw. SG Dominika Tracza. Stanowisko komendanta NOSG pełnił do 16 października 2015 r.
Gen bryg. SG Wojciech Skowronek na stanowisko Komendanta NOSG został powołany dnia 16 października 2015 roku przez Komendanta Głownego Straży Granicznej gen. dyw. SG Dominika Tracza. Stanowisko komendanta NOSG pełnił do 22 sierpnia 2017 r.