Родился 21 мая 1973 года в Пензе.
В 1992 году окончил Ленинградское высшее политическое училище имени 60-летия ВЛКСМ внутренних войск МВД СССР.
В 1997 г. окончил Пензенский государственный педагогический университет им. В. Г. Белинского (ПГПУ; с 2012 г. — Педагогический институт им. В. Г. Белинского Пензенского государственного университета) по специальности «учитель истории и социально-политических дисциплин», в 2009 г. — Пензенский государственный университет по специальности «юрист».
В 2016 г. в Башкирском государственном университете прошел профессиональную переподготовку по программе «менеджмент в образовании«. В 2019 г. прошел обучение в Российской академии народного хозяйства и государственной службы при президенте РФ (программа развития кадрового управленческого резерва), в 2020 и 2021 гг. — в Дипломатической академии МИД России (специалист в области мировой политики и мировой экономике).
Выпускник второго потока программы подготовки кадрового управленческого резерва государственной службы, созданной на базе Высшей школы государственного управления (т. н. школы губернаторов).
Кандидат исторических наук. В 2006 г. в ПГПУ им. В. Г. Белинского защитил диссертацию по теме «Кризис системы управления КПСС 1985-1991 годов в Пензенской области». Доцент.
С 1997 по 2001 г. — преподаватель-стажер, ассистент, старший преподаватель кафедры истории древнего мира, средних веков и археологии исторического факультета Пензенского государственного педагогического университета им. В. Г. Белинского.
В 2001-2004 гг. — заместитель главы администрации Железнодорожного района Пензы по социальной политике и взаимодействию с правоохранительными органами.
С сентября 2004 г. по январь 2006 г. — специалист-эксперт департамента по внутренней политике аппарата полномочного представителя президента РФ в Дальневосточном федеральном округе, ДФО (в 2000-2005 гг. пост полпреда в ДФО занимал Константин Пуликовский, в 2005-2007 гг. — Камиль Исхаков).
С января по ноябрь 2006 г. Олег Мельниченко возглавлял отдел по связям с общественностью правительства Пензенской области.
С ноября 2006-го по январь 2007-го — начальник управления по вопросам национальной политики, связям с общественными и религиозными объединениями правительства Пензенской области.
С января по апрель 2007 года был советником департамента по кадровым вопросам и организационному обеспечению аппарата полномочного представителя президента РФ в Приволжском федеральном округе (ПФО) (пост полпреда в этот период занимал Александр Коновалов).
С апреля 2007-го по январь 2008-го — министр образования Пензенской области (глава региона в 1998-2015 гг. — Василий Бочкарев).
С января по июнь 2008 г. — вице-губернатор Пензенской области. С июня 2008 по апрель 2009 г. — заместитель председателя правительства региона.
С апреля 2009 года по сентябрь 2013 года занимал пост помощника полномочного представителя президента РФ в ПФО. Округ в 2008-2011 гг. возглавлял Григорий Рапота, в 2011-2018 гг. — Михаил Бабич. С сентября 2013 г. по сентябрь 2017 г. Олег Мельниченко был заместителем полпреда президента РФ в Приволжском федеральном округе.
10 сентября 2017 г. был избран депутатом Законодательного собрания Пензенской области VI созыва. Баллотировался в составе списка кандидатов от регионального отделения партии «Единая Россия» (третий номер в списке).
С 26 сентября 2017 г. по 31 марта 2021 г. был членом Совета Федерации РФ (сенатором), представителем от Законодательного собрания Пензенской области. С 25 октября 2017 г. возглавлял комитет Совфеда по федеративному устройству, региональной политике, местному самоуправлению и делам Севера. Входил во временную комиссию Совфеда по защите государственного суверенитета и предотвращению вмешательства во внутренние дела РФ (с марта 2019 г.). Руководил группой по сотрудничеству Совета Федерации с Верховным народным собранием КНДР, был членом групп сотрудничества Совфеда с верхними палатами парламентов Экваториальной Гвинеи, Словацкой и Чешской республик. Занимал пост заместителя сопредседателя межпарламентской комиссии по межрегиональному сотрудничеству с Национальным собранием Республики Белоруссия. Представлял РФ в Палате регионов Конгресса местных и региональных властей Совета Европы (с 2019 г.).
С 25 декабря 2017 г. — председатель Всероссийского совета местного самоуправления (ВСМС). С мая 2019 г. — первый заместитель председателя высшего совета Всероссийской ассоциации развития местного самоуправления.
С 2021 г. возглавляет Пензенскую область. 26 марта 2021 г. указом президента РФ назначен врио губернатора Пензенской области. Прежний руководитель региона Иван Белозерцев, обвиняемый в получении взятки, 23 марта был отправлен в отставку в связи с утратой доверия главы государства.
19 сентября 2021 г. на досрочных выборах был избран губернатором Пензенской области (выдвинут от партии «Единая Россия») с результатом 72,38%. Второе место занял заместитель главы Пензы Олег Шаляпин (КПРФ), за которого проголосовали 12,35% избирателей. 28 сентября Олег Мельниченко вступил в должность.
Член советов при президенте РФ по межнациональным отношениям (с января 2018 г.), по развитию местного самоуправления (с февраля 2018 г.), по стратегическому развитию и национальным проектам (с апреля 2020 г.). Входит в состав комиссий при правительстве РФ по региональному развитию (с июля 2018 г.), по развитию жилищного строительства и оценке эффективности использования земельных участков, находящихся в собственности Российской Федерации (с марта 2020 г.).
Член президиума генерального совета партии «Единая Россия» (с декабря 2017 г.). Секретарь пензенского регионального отделения партии (с июня 2021 г.).
Действительный государственный советник РФ II класса (2014).
Награжден орденом Дружбы (2020), медалью ордена «За заслуги перед Отечеством» II степени (2015). Имеет две благодарности президента РФ (2012, 2018), Почетную грамоту правительства РФ (2020).
Почетный работник высшего профессионального образования РФ.