Jednopokładowy okręt miał mieć zdolność pływania przy stanie morza 6 i desantowania przy stanie morza 2, a jego ładownia mogła zmieścić sprzęt wojskowy o masie 183 ton w postaci czterech czołgów ciężkich (IS-2) albo pięciu średnich (T-34/85) lub pływających (PT-76), a zamiennie także trzech haubic kalibru 122 lub 152 mm, dziewięciu samochodów ciężarowych (ZiS-151) i 19 samochodów terenowych (GAZ-69). Zamówienie na budowę jednostek projektu 770D zostało złożone w Stoczni Północnej im. Bohaterów Westerplatte w Gdańsku, która 15 lipca 1961 roku rozpoczęła prace nad okrętem prototypowym o numerze stoczniowym 770D/1. Po wejściu do służby we Flocie Czarnomorskiej w 1962 roku otrzymał oznaczenie SDK-22. Wkrótce w stoczni rozpoczęto budowę serii kolejnych 14 okrętów, z których dziewięć miało trafić pod polską banderę (jednostki z numerami stoczniowymi 770D/5, 6, 7, 10, 11, 12, 13, 14 i 15).
Przyszły ORP „Wisła” zbudowany został w Stoczni Północnej im. Bohaterów Westerplatte w Gdańsku (numer stoczniowy 770D/11). Stępkę okrętu położono 14 sierpnia 1963 roku, a zwodowany został 29 sierpnia 1964 roku. Jednostka otrzymała nazwę rzeki związanej z historią polskiej wojskowości – Wisły.