ORP „Mewa” zbudowana została w Stoczni im. Komuny Paryskiej w Gdyni (numer stoczniowy 206F/11). Nadzór wojskowy nad budową sprawował kmdr ppor. inż. Konstanty Cudny. Stocznia zastosowała metodę budowy kadłuba jednostki z sekcji, łączonych na pochylni (opracowaną wcześniej w celu masowej budowy trawlerów). Stępkę okrętu położono 18 lipca 1966 roku, a zwodowany został 22 grudnia 1966 roku. Trałowiec otrzymał tradycyjną dla polskich okrętów minowych nazwę pochodzącą od ptaka – mewy. Matką chrzestną jednostki była żona oficera Marynarki Wojennej Irena Ciećkowska.
Dane taktyczno-techniczne Okręt był gładkopokładowym, pełnomorskim trałowcem, przystosowanym do pływania w warunkach częściowego oblodzenia. Długość całkowita wynosiła 58,2 metra, szerokość 7,97 metra i zanurzenie 2,14 metra. Wysokość boczna miała wielkość 4 metrów. Wykonany ze stali, całkowicie spawany kadłub jednostki został wzmocniony w celu zwiększenia odporności na podwodne wybuchy.