В 1954 году Валуцкий поступил на сценарный факультет, в мастерскую Евгения Габриловича. Но студенческий путь был непростым: учился до 1959 г., затем был отчислен и два года работал режиссёром в кинолаборатории ВНИИ Стройдормаша (был одним из создателей лаборатории). Позже, в 1960 году, вернулся во ВГИК, чтобы завершить начатое, и окончил заочное отделение в 1964 году. То был осознанный выбор — остаться в профессии, несмотря на все изгибы маршрута.
Первые сценарии Валуцкого — проба голоса, в которой уже слышна будущая интонация мастера. «Постоянно прописаны» (совм. с А. Шеиным, сюжет в «Фитиле» № 27, 1964) — острая, лаконичная зарисовка, где проявились юмор и наблюдательность. За ней последовал «Комэск» (совм. с М. Коршуновым, реж. Геннадий Костюков, 1965) — работа, в которой уже чувствовалось умение выстраивать характеры и напряжение внутри простых обстоятельств.
Первые громкие победы пришли вместе с режиссёром-дебютантом Виталием Мельниковым. В 1966 году на экраны вышел «Начальник Чукотки» — фильм, покоривший зрителя. Далее последовали работы, в каждой из которых Валуцкий будто примерял новый регистр: «Тихая Одесса» (1967, реж. Валерий Исаков) — с её особой интонацией памяти и пространства; «Завтра, третьего апреля» (1969, реж. Игорь Масленников) — тонкая, почти камерная история о подростках; и, наконец, «Семь невест ефрейтора Збруева» (1970). В новой совместной с Мельниковым работе — в живом, ироничном роуд-муви о незадачливом ефрейторе, которое держалось на крепкой драматургической основе и умении автора слышать живую речь, — закрепился успех Валуцкого как мастера лирической комедии. В архивах ВГИКа бережно хранятся свидетельства тех лет: фотографии рабочих моментов со съёмок — немые, но красноречивые хроники кинопроцесса, киноплакаты.