W 1960 zbudowano prototyp samolotu „128”, który oblatano 18 marca 1961. 9 lipca 1961 został zaprezentowany na paradzie lotniczej w Tuszynie pod Moskwą z makietami pocisków, po czym nadano mu na zachodzie nazwę kodową ‘Fiddler’. Równolegle z budową prototypu, już pod koniec 1959 rozpoczęto przygotowania do produkcji seryjnej w zakładzie nr 64 w Woroneżu i na początku 1961 ukończono budowę pierwszego samolotu przedseryjnego, oblatanego 13 maja 1961. W 1961 i 1962 zbudowano jeszcze kilka samolotów, na których wprowadzano od razu zmiany zgodnie z wynikami prób w locie. Od 20 marca 1962 prowadzono próby państwowe samolotu, m.in. 27 września 1962 miało miejsce pierwsze zestrzelenie zdalnie sterowanego latającego celu Ił-28.
12 grudnia 1963 minister obrony zmienił oznaczenie samolotu na Tu-128, przy czym cały kompleks rakietowy otrzymał oznaczenie Tu-128S-4, a pociski K-80 oznaczenie R-4. Długotrwałe badania państwowe ukończono we wrześniu 1964 i 30 kwietnia 1965 kompleks Tu-128S-4 oficjalnie przyjęto na uzbrojenie.