Багато подорожував із коханою дружиною, творчою колегою, художницею Адою Рибачук. Їхня перша подорож на Північ відбулася в 1954 р., почавшись з берегів Білого моря та продовжившись на острові Колгуєв. Подорож надихнула митця обрати відповідну тему дипломної роботи — «Зимовий берег Білого моря. Острів Колгуєв». Наступна експедиція на Північ, в яку відправилось подружжя Мельниченко-Рибачук у 1955 р., тривала півтора року.

Захист дипломів Мельниченко та Рибачук навесні 1957 р. фактично був першою персональною виставкою художників. Тут Володимир Мельниченко продемонстрував масштабні роботи «Перше вересня» і «Північне море», а також етюди, зроблені на Півночі.

Третя, найдовша експедиція на Північ Володимира Мельниченка і Ади Рибачук відбулася в 1957-1959 рр. У 1959 р. подружжя подарувало місту Нар’ян-Мар 118 своїх творів, які стали основою першого художнього музею в Арктиці. Сьогодні в фондах музею налічується 237 творів Володимира Мельниченко і Ади Рибачук.

Разом із дружиною Володимир Мельниченко працював над монументально-декоративним оформленням київського автовокзалу, отримавши за це Першу Всесоюзну премію молодих архітекторів за інтер’єри. Разом подружжя опрацьовувало й концепцію оформлення Республіканського палацу піонерів, брали участь в конкурсі на проект пам’ятника «Жертвам фашизму» в Бабиному Яру. Вони створили меморіально-обрядовий комплекс «Парк Пам’яті» на Байковому кладовищі, витративши на реалізацію задуму майже тринадцять років. Спроєктували разом історико-археологічний парк «Стародавній Київ». Такі проєкти вимагали вивчення народних звичаїв, обрядів — тож Мельниченко з дружиною подорожували Волинню, Поділлям, Буковиною, щоби в результаті передати власні враження в серіях естампів.

У 1982 р. держ.органами було прийнято рішення припинити монументально-декоративні роботи в Парку Пам’яті, назвавши причиною невідповідність «принципам соціалістичного реалізму» — це фактично знищувало Стіну Пам’яті. Впродовж весни наступного року рельєфи Мельниченка і Рибачук було замуровано бетоном.

Спільно з дружиною Мельниченко створили цикл великих керамічних скульптур «Бронзові образи», серії літографій «Пам'ять» та «Зупинити ядерну загрозу» (подарували ці роботи Національному художньому музею України), склали меморіальний цикл під назвою «Пам’яті Друзів», працювали над проектом «Коли руйнується світ», який присвятили пам’яті жертв Бабиного Яру (складається з книги та трьох гобеленів). Працюючи в творчому тандемі з дружиною Адою Рибачук, митці втілювали свої ідеї, думки, враження, емоції в живописі, монументальних творах, архітектурі, скульптурі, фільмах. Спільні роботи Мельниченко і Рибачук підписували абревіатурою АРВМ.

У травні 2018 р. було відкрито 6 м² фрагменту Стіни Пам'яті. А в 2021 р. вдалося відновити композицію «Берегиня».