W 1932 wstąpił na Politechnikę Kijowską (8 lat wcześniej studiował na niej Siergiej Korolow), gdzie szybko zaczął się wybijać. W 1936 opublikował pierwszą pracę naukową, Analizę wektorową. W wieku 24 lat miał już na koncie 14 publikacji. W tym samym czasie uczęszczał na wykłady z analizy matematycznej, rachunku różniczkowego, fizyki matematycznej, teorii elastyczności i mechaniki, na Uniwersytecie Kijowskim. Był również słuchaczem wykładów Tullio Leviego-Civity w Akademii Nauk Ukraińskiej Republiki Radzieckiej. W tym czasie Czełomiej zainteresował się mechaniką i teorią oscylacji, którymi parał się przez resztę życia. Uczelnię skończył w 1937 roku z wyróżnieniem. Następnie pracował jako wykładowca i w 1939 obronił dyplom kandydata nauk (doktorski). W 1940 otrzymał jedno z 50 rocznych stypendiów Stalina.
II wojna światowa W 1941 roku wstąpił do WKP(b). W czasie wojny Czełomiej pracował w Centralnym Instytucie Budowy Silników Lotniczych im. Baranowa (TsIAM) w Moskwie. Dzięki wsparciu Wolikowa, ministra lotnictwa ZSRR, założył zespół konstrukcyjny, którego prace doprowadziły do budowy w 1942 roku, niezależnie od inżynierów niemieckich, pierwszego silnika pulsacyjnego.