ТТЗ на проектирование корабля выдано весной 1949 г., эскизный проект разработан в том же году, технический — в 1950 г., головной корабль заложен в 1951 г. Ввиду несвоевременной поставки оборудования постройка корабля задержалась до 1957 г. За это время стала обязательной (с 1954 г.) реализация на всех строящихся кораблях требований ПАЗ, а также появились новые образцы вооружения и оборудования. В связи с этим заказчик выдал в 1956 г. ТТЗ на корректировку проекта (пр. 264А), по которому в 1958—1962 гг. было построено 23 корабля.
Корабль пр. 264 по архитектурному типу и компоновке общего расположения напоминал корабли пр. 254. В отличие от последних на них предусматривалось новое вооружение, почти вдвое более мощные ЭУ и ЭЭУ с эшелонным расположением, ЭЭУ на переменном токе напряжением 220 В, уменьшенные габариты надстройки за счет переноса рубок радиолокации и радиосвязи под верхнюю палубу, надстройка из алюминиевого сплава, увеличение автономности и улучшение условий обитаемости (блок медицинских помещений, воздушное отопление жилых и части служебных помещений) и др.
В отличие от кораблей пр. 264 на кораблях пр. 264А предусматривались: ПАЗ (в более широком объеме, чем на кораблях пр. 254Л), замена части вооружения и оборудования, дополнительные мероприятия по снижению ФП (усовершенствованное РУ, обклейка резиновым покрытием внутренних стенок машинных отделений и фундаментов дизелей, дизель-генераторов, воздушное экранирование вращающихся гребных винтов и др.), увеличение мощности стояночного дизель генератора, переход на переменный ток напряжением 380 В, установка рефрижераторного aгperaтa и др. Из-за наличия стального корпуса, завышенных требований к условиям обитаемости и завышения проектантом в расчетах масс оборудования (по сравнению с поставками) корабли оказались недостаточно эффективными как ТЩ: они были недостаточно защищены от подрыва на неконтактных минах и подвержены ветровому сносу. 12 построенных кораблей сразу же были переданы морпогранохране, три переоборудованы в корабли радиолокационного дозора (пр. 963), по одному кораблю было передано Гвинее и Южному Йемену.
К 1975 г. оставшиеся корабли были переоборудованы в СКР и спасательные суда. В корпусах пр. 264А в 1959—1963 гг. на заводе № 363 были построены 13 спасательных судов по пр. 532 и 532У, одно из которых передано Индии. К 1990 г. все корабли пр. 264 и 264А были вы ведены из состава ВМФ.