W 1959 roku CKBO nr 2 opracował zmodyfikowany projekt trałowca o wyporności 425 ton, którego napęd miały stanowić włoskie silniki wysokoprężne FIAT, wobec braku odpowiednich jednostek napędowych produkowanych w państwach socjalistycznych. Projekt (pod oznaczeniem B206F) został przyjęty do realizacji w grudniu 1959 roku przez Ministra Obrony Narodowej, lecz ostateczny projekt techniczny zatwierdzono w Dowództwie MW dopiero 19 lutego 1962 roku. Koszty dokumentacji wyniosły 1,7 mln zł, budowa prototypu (przyszłego „Orlika”) kosztowała 80 mln zł, a koszt seryjnego okrętu wyniósł 65,5 mln zł. Roczny limit eksploatacyjny jednostki określono na 700 godzin, a żywotność konstrukcji na 20 lat.
ORP „Czajka” zbudowana została w Stoczni im. Komuny Paryskiej w Gdyni (numer stoczniowy 206F/12). 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 12 września 1966 roku, a zwodowany został 17 grudnia 1966 roku. Trałowiec otrzymał tradycyjną dla polskich okrętów minowych nazwę pochodzącą od ptaka.