Chelomei naceu en 1914 na cidade ucraína de Sedlets, nunha familia de mestres que tivo que migrar a Paltava tres meses despois debido á primeira guerra mundial. Á edade de 12 anos, a familia de Chemolei tivo que moverse a Kíiv, onde estudou mecánica de automóbiles. En 1932 entrou no politécnico de Kíiv, a mesma institución na que Koroliov estudara oito anos antes. Considerado un prodixio, aos 22 publicou o seu primeiro libro (Análise de vectores) e aos 24 publicara xa 14 artigos científicos. En 1941 uniuse ao Partido Comunista e obteu o seu doutoramento, sendo nomeado xefe do Grupo de Propulsión a Chorro do Instituto Central P. I. Baranov de Aviación a Propulsión (TsIAM polas súas siglas en ruso).
Chelomei inventou de maneira independente o pulsorreactor en 1942. En xuño de 1944 foi invitado a analizar os restos dun mísil V-1 alemán e encargouselle reproducilo, tarefa que acadou a finais dese mesmo ano, creando o mísil 10-Kh. O 17 de setembro se lle asignou a súa propia oficina de deseño. Cara 1958 Chelomei traballara no desenvolvemento dun novo mísil de cruceiro ao tempo que empezaba a demostrarse a superioridade dos mísiles balísticos intercontinentais sobre os de cruceiro. Tamén nese ano comezou a ter contacto coas altas esferas do Kremlin, trabando amizade co fillo de Nikita Khrushchev, o que lle permitiu expoñer as súas ideas directamente a altos cargos. En 1952 foi nomeado profesor na Universidade Baumann e en 1959 deuselle o alto cargo de Deseñador Xeral da oficina OKB-52.
Chelomei innovou no campo dos mísiles desenvolvendo o concepto de mísil encapsulado e almacenable a largo prazo capaz de ser lanzado en cuestión de minutos despois da orde de disparo. Propuxo a construción do mísil UR-100, a resposta ao mísil Minuteman estadounidense, e cara finais da década de 1950 comezou a pensar en como usar a tecnoloxía de mísiles en foguetes e naves espaciais. Ideou varios avións espaciais e lanzadores pesados, entre eles o UR-500, que daría lugar ao foguete Proton. Tamén lanzou o programa de estacións militares Almaz e as naves tripuladas TKS.
Chelomei faleceu o 28 de decembro de 1984 debido a unha trombose inesperada nun hospital de Moscova tras ser trasladado ao mesmo por un accidente na súa casa.
