Оставаясь в Москве, в 1943 году Вадим поступает на поэтическое отделение Литературного института, где тогда, в первой половине сороковых годов, кипели довольно бурные литературные страсти.
Подошла к концу война. И Коростылёв принял решение: коль судьба не дала ему повоевать, он всё равно наверстает упущенное. На последнем курсе он уходит из института и уезжает в Арктику, где два года руководит одной из зимовок Карской научно-промысловой экспедиции. Продолжает писать стихи и в 1947 году приезжает в Москву на Всесоюзное совещание молодых писателей как делегат Крайнего Севера.
По возвращении с севера Вадим женился. Жена писателя, Заира, была дочерью расстрелянного в 1938 году советского экономиста, члена Коминтерна, организатора Коммунистической партии Ирана Аветиса Султан-Заде. В начале 1954 года у Коростылёвых родилась дочь. Нужно кормить семью. Заработок приносили водевили, бурлески, пьесы для детского театра и тексты песенок для кинофильмов.
Новогодняя комедия Эльдара Рязанова «Карнавальная ночь» сделала Коростылёва знаменитым: «И улыбка, без сомненья, вдруг коснётся ваших глаз…» – распевала вся страна.
В 1955 году Олег Ефремов поставил в Центральном детском театре озорной и весёлый музыкальный спектакль Коростылёва и Львовского «Димка-невидимка». А в 1957-м в ТЮЗе Ролан Быков выпускает полную эксцентрики постановку по пьесе Коростылёва «О чём рассказали волшебники». Спектакль получил множество всяких премий, в том числе и международных. Эти спектакли стали режиссёрскими дебютами и Ефремова, и Быкова. Потом случилось так, что один из режиссёров-«волшебников» – Ролан Быков – ушёл работать в кино, и тогда Коростылёв пересочинил эту сказку для кинематографа. А песенка из «Айболита-66» стала негласным гимном советской интеллигенции: «Это очень хорошо, что нам очень плохо!!!»
Однажды писателя спросили: «Как вы пришли в сказку?» – «Да кто его знает, как это происходит, – ответил он. – Мне просто захотелось сказок!»
И действительно, драматург заселяет свои пьесы и сценарии не только влюблёнными да властителями сказочных царств. В них активно действуют обезьянки, собаки, птицы, мыши. Но не только этот звериный мир очеловечивается. Души деревьев и грибы, сорняки и цветы, а также куклы, пузырьки из-под чернил, подземные минералы – вся эта разнообразнейшая сказочная братия имеет совершенно живые человеческие характеры: они умеют любить и ненавидеть, приходить на помощь или предавать ближних своих… В общем, всё как у людей.