Powstał w 1953 jako klub koszarowy, w 1957 otrzymał rangę klubu garnizonowego. Reprezentacyjny obiekt powstał w 1952-53, posiada ciekawą socrealistyczną architekturę - w monumentalnej 25-osiowej fasadzie centralny 5-osiowy ryzalit z arkadowymi podcieniami, kolistym fryzem i murem attykowym ze sterczynami, taras z tralkową balustradą, w holu kolumny i dwuskrzydłowe schody.
Mieścił kino, w 1960-91 ogólnomiejskie "Dedal", kawiarnię, bibliotekę (2010 - 40 tys. tomów), księgarnię. W 1968 działało w nim koło dramatyczne, lalkowe, instrumentalno-wokalne, plastyczne. Działały tam zespoły "Lotos", "Orion", znaną postacią był kierownik w Klubie mjr Stefan "Steve" Kozłowski. Odbywały się tam znane bale sylwestrowe, wystawy (m.in. filatelistyczne), koncerty, od 2002 corocznie trzydniowy Festiwal Twórczości Dziecięcej Okręgu Wojskowego. W podpiwniczeniu mieści się strzelnica.
Był klubem otwartym, służącym mieszkańcom miasta, w reprezentacyjnej sali widowiskowej odbywały się nie tylko imprezy kulturalne, ale także zjazdy, konferencje, uroczystości państwowe. Z gościnności klubu korzystało do 2010 kino "Stylowy". Z końcem 2010 stał się Klubem Batalionowym.
W 1979-90 w fasadzie budynku tablica poświęcona powstaniu w 1918. Od 2018 przed fasadą pomnik marszałka J. Piłsudskiego.
Pierwszym kierownikiem był por. Marian Południak, 1955-58 por. Zbigniew Dziuk, kolejnymi (w stopniu kapitana) 1958-59 Jan Kaźmierczak, 1959-61 Eugeniusz Buczkowski, 1961-63 Marian Lewandowski, 1963-71 Leon Kozłowski, 1971-73 Wiesław Kuśmider, 1973-84 Franciszek Smoter, 1984-93 Wiesław Parafiniuk, ostatnim Janusz Kupczyk, ob. kier. KB Agnieszka Biernacka. Od 1959 działał też Klub Żołnierski (pierwszym kierownikiem Marian Lewandowski).
* W 2017 KB zwyciężył w konkursie na najlepszy klub batalionowy w Polsce. Działa przy nim Chór Ziemi Zamojskiej "Contra", Nieetatowa Orkiestra Wojskowa i koło PTTK "Iskra".