Początkowo ustalono, żeby powierzyć budowę okrętów Stoczni Północnej w Gdańsku z uwagi na jej duże doświadczenie w budowie jednostek tego rodzaju oraz istnienie odpowiedniego zaplecza technicznego; dodatkowo za budową tam okrętów przemawiał fakt, iż stocznia ta dostarczyła udane jednostki projektu 902. Jednak ostatecznie budowę patrolowców powierzono gdyńskiej Stoczni Marynarki Wojennej. Decyzja ta zapadła najprawdopodobniej na szczeblu politycznym. Na przełomie lat 1963–1964 odbyło się przekazanie odpowiedzialności oraz dokumentacji za budowę okrętów między stoczniami w celu rozpoczęcia ich budowy.
Z początkiem 1964 roku Szefostwo Służby Morskiej Wojsk Ochrony Pogranicza zamówiło pięć okrętów, które zbudowane miały być w latach 1965–1967. W wyniku braku doświadczonej kadry pracowniczej oraz braku zaplecza technologicznego budowa przebiegała z licznymi problemami. Dotyczyły one m.in. pozyskania wykwalifikowanych pracowników do stoczni oraz rosnących kosztów przygotowań do rozpoczęcia budowy. Finalnie w maju 1964 roku udało się uzgodnić warunki umowy na opracowanie dokumentacji technicznej, budowy oraz przekazania odbiorcy okrętów, które zgodnie z jej zapisami dostarczone miały być do września 1967 roku. Budowa okrętu prototypowego rozpoczęła się w lipcu 1964 roku, a wodowanie jego kadłuba odbyło się 29 kwietnia 1965 roku.