Для скорейшего насыщения флота ракетным оружием решено было продолжить серию ракетных кораблей в корпусе эсминца пр. 56.
По результатам испытания пр. 56Э ЦКБ-53 под руководством того же О.Ф.Якоба, минуя стадию технического проектирования, разработало документацию пр. 56М.
Весь состав вооружения оставался таким же, как и на пр. 56ЭМ, за исключением замены 45-мм автоматов на более мощные 57-мм автоматы ЗИФ-75.
Головной «Прозорливый» был заложен 1 сентября 1955 г. и сдан флоту 30 декабря 1958 г. За ним были дооборудованы по этому же проекту «Неуловимый» и «Неудержимый», оба заложенные как чисто артиллерийские корабли.
Их тактико-технические данные были следующие. Водоизмещение: стандартное — 2767 т, полное — 3315 т. Размеры: длина — 126 м, ширина — 12,7 м, осадка — 4,5 м. Мощность энергетической установки, котлотурбинной — 2x36000 л.с. Скорость — 39 уз. Дальность плавания 3900 миль при скорости в 14 уз. Автономность 10 суток. Экипаж 270 человек.