В марте 1946 года Наркомат нефтяной промышленности был разделен на Министерство нефтяной промышленности южных и западных районов СССР и Министерство нефтяной промышленности восточных районов. Байбаков возглавил первое. На этом посту ему пришлось столкнуться с целым рядом проблем, и одной из острейших была кадровая.
Когда в декабре 1948 года топливные министерства объединили, Байбаков стал министром нефтяной промышленности СССР. Ведомство управляло также газовой промышленностью. И здесь послужной список Байбакова пополнился строительством газопровода Саратов — Москва. Его история такова. В годы войны потребности московских предприятий и населения в топливе покрывались в основном за счет дров, торфа и топочного мазута, поскольку Донбасс — основной довоенный поставщик каменного угля — был оккупирован, а после освобождения его еще предстояло восстановить и вернуть к жизни. Многие жители Москвы того времени — в основном, женщины — были заняты на лесозаготовках. Дрова по столице развозили грузовые трамваи, за керосином выстраивались огромные очереди. Поэтому 3 сентября 1944 года Сталин подписал постановление ГКО «О строительстве газопровода Саратов — Москва».
За проект отвечало Министерство нефтяной промышленности, а работы были поручены Главному управлению аэродромного строительства НКВД. Возглавляли строительство генерал-лейтенант Л. Б. Сафразян и генерал-майор инженерной службы В. А. Панкин. Из США по лендлизу были поставлены тонкостенные бесшовные трубы, газоперекачивающие агрегаты и другое оборудование. А в декабре 1944 года Байбаков получил разрешение на отправку в США нескольких министерских сотрудников для закупки 25 газотурбинных компрессоров «Cooper-Bessemer 1591 GMV», а также для изучения опыта строительства и эксплуатации дальних газопроводов. Группу возглавил Юлий Боксерман — крупный газовый специалист, один из самых верных подручных Байбакова.