ORP „Żubr” zbudowany został w Stoczni im. Komuny Paryskiej w Gdyni. Stępkę okrętu położono 18 marca, a zwodowany został 23 czerwca 1956 roku. Trałowiec otrzymał nazwę pochodzącą od zwierzęcia lądowego – żubra, łamiąc zasady dotychczasowego nazewnictwa okrętów tej klasy w Marynarce Wojennej, nawiązujące do ptaków i zwierząt morskich.
Dane taktyczno-techniczne Okręt był dużym, pełnomorskim trałowcem. Długość całkowita wynosiła 58 metrów (54 metry na konstrukcyjnej linii wodnej), szerokość 8,5 metra i zanurzenie 2,3 metra. Wykonany ze stali, całkowicie spawany kadłub jednostki podzielony był na jedenaście przedziałów wodoszczelnych (od dziobu): I – forpik i magazyn, II – komora łańcuchowa i magazyn żywności, III – pomieszczenia mieszkalne i służbowe oraz magazyny, IV – zbiorniki i pomieszczenia załogi, V – komora amunicyjna, VI – mechanizmy pomocnicze, VII – maszynownia, VIII – magazyny i komora amunicyjna, IX – wały napędowe i pomieszczenia załogi, X – magazyn trałowy i XI – maszyna sterowa i magazyny: chemiczny i mundurowy. W przebiegającym niemal na całej długości kadłuba dnie podwójnym mieściły się zbiorniki paliwa, wody i zęzy. Pod podwyższonym pokładem dziobowym znajdowały się kolejno: magazyn farb, urządzenie kotwiczne, jadalnia oficerska, kabiny oficerów i pomieszczenia podoficerskie.