Główne zmiany w stosunku do wersji K 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 „Ryś” zbudowany został w Stoczni im. Komuny Paryskiej w Gdyni. Stępkę okrętu położono 12 stycznia, został zwodowany 29 kwietnia, a do służby w Marynarce Wojennej wszedł 10 września 1959 roku. Trałowiec otrzymał nazwę pochodzącą od zwierzęcia lądowego – rysia, łamiąc zasady dotychczasowego nazewnictwa okrętów tej klasy w Marynarce Wojennej, nawiązujące do ptaków i zwierząt morskich.