Po śmierci Stalina i Berii w 1953, o Czełomieju przypomniał sobie Gieorgij Malenkow. Czełomiej przekonał sekretarza partii do idei skrzydlatych rakietowych pocisków przeciwokrętowych, które mogłyby być wystrzeliwane z okrętów nawodnych i podwodnych. Dla Armii Radzieckiej była to świetna propozycja zrównoważenia amerykańskiej dominacji na morzach.
Dekretem ministra przemysłu lotniczego z 9 sierpnia 1954 roku Czełomiej został mianowany dyrektorem Specjalnej Grupy Projektowej (ros. SKG) w zakładach silnikowych nr 500 w Tuszynie pod Moskwą. W lipcu 1955 roku SKG przekształcono w biuro projektowe OKB-52 pod kierownictwem Czełomieja jako głównego konstruktora. Biuro przeniesiono do niewielkich zakładów mechanicznych w Rieutowie pod Moskwą, gdzie kontynuowało podjęte z własnej inicjatywy prace nad nowymi skrzydlatymi pociskami rakietowymi dla okrętów podwodnych.
W 1955 roku Czełomiej uzyskał zlecenie na opracowanie skrzydlatego pocisku strategicznego P-5. Pocisk ten okazał się lepszy od konkurencyjnego P-10 Bierijewa i w 1959 roku został przyjęty na uzbrojenie. Za skonstruowanie pocisku P-5 Czełomiej w 1959 roku otrzymał tytuł Bohatera Pracy Socjalistycznej i wraz z zespołem Nagrodę Leninowską.