Główne zmiany w stosunku do wersji 254K polegały na wzmocnieniu uzbrojenia (w miejsce czterech podwójnych stanowisk 2M-1 wkm kal. 12,7 mm zamontowano dwa podwójne zestawy działek automatycznych 2M-3M kal. 25 mm i dwa zdwojone stanowiska 2M-7 wkm kal. 14,5 mm, a miotacze bomb głębinowych typu BMB-1 zastąpiły nowsze BMB-2) oraz instalacji nowocześniejszego wyposażenia trałowego (trały kontaktowe MKT-1, akustyczne BGAT i elektromagnetyczny TEM-52M). Okręty miały też inny kształt rufy i związaną z tym większą o 1 metr długość kadłuba. Plany zakładały budowę serii liczącej aż 27 jednostek projektu 254, jednak zawirowania z wersjami i odwilż październikowa sprawiły, że poprzestano na 12 trałowcach (trzech projektu 254K i dziewięciu projektu 254M).
ORP „Foka” zbudowany został w Stoczni im. Komuny Paryskiej w Gdyni (numer budowy B4/106). Stępkę okrętu położono 24 maja 1958 roku, a zwodowany został 22 sierpnia tego roku. Trałowiec otrzymał nazwę pochodzącą od zwierzęcia wodnego – foki.