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ł, a budowa prototypu (czyli przyszłego „Orlika”) kosztowała 80 mln zł. Roczny limit eksploatacyjny jednostki określono na 700 godzin, a żywotność konstrukcji na 20 lat.
ORP „Albatros” zbudowany został w Stoczni im. Komuny Paryskiej w Gdyni (numer stoczniowy 206F/6). 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 8 czerwca 1964 roku, został zwodowany 15 kwietnia 1965 roku. Trałowiec otrzymał tradycyjną dla polskich okrętów minowych nazwę pochodzącą od ptaka.