Родился 8 июня 1966 г. в г. Запорожье Украинской ССР в рабочей семье.
В 1990 г. окончил филологический факультет Киевского государственного университета им. Т.Г. Шевченко (ныне Киевский национальный университет им. Тараса Шевченко) по специальности "преподаватель и референт-переводчик". С 1991 г. по 1994 г. был слушателем Института КГБ СССР им. Ю.В. Андропова (ныне Академия внешней разведки). 15 февраля 1994 г. был отчислен из института, согласно поданному рапорту.
В 1990–1991 гг. работал преподавателем русского языка для иностранных студентов в Киевском инженерно-строительном институте.
С 1992 г. по 1994 г. был заместителем директора по экономике, маркетингу и менеджменту ООО "Качество" в Запорожье.
В 1994–1997 гг. занимал должность второго секретаря, затем первого секретаря консульского отдела Посольства Украины в Финляндии (по совместительству в Дании и Норвегии).
В 1997 г. стал сотрудником Консульского управления Департамента консульской службы МИД Украины. Занимал должности первого секретаря, советника, заведующего отделом и заместителя начальника управления.
С 2001 г. по 2003 г. - генеральный консул (советник) Посольства Украины в США.
В 2003-2004 гг. - директор Департамента консульской службы МИД Украины.
В 2004-2005 гг. занимал должность заместителя министра иностранных дел Украины в правительстве Виктора Януковича.
В 2006 г. был Чрезвычайным и Полномочным Послом Украины в Белоруссии.
В 2006–2009 гг. - первый заместитель председателя Службы безопасности Украины (СБУ) - руководитель Антитеррористического центра при СБУ Украины.
С декабря 2006 г. по март 2009 г. исполнял обязанности председателя СБУ.
С 6 марта 2009 г. по 11 марта 2010 гг. занимал пост председателя СБУ Украины.
В 2007–2010 гг. входил в состав Совета национальной безопасности и обороны Украины.
С 2010 г. по 2012 г. возглавлял политический совет партии "Наша Украина". 24 мая 2012 г. сложил с себя полномочия главы политсовета и остановил свое членство в партии.
В августе 2012 г. вступил в партию "УДАР Виталия Кличко".
В октябре 2012 г. избран депутатом в Верховную Раду VII созыва от партии "УДАР Виталия Кличко". Помощником Валентина Наливайченко в парламенте был Дмитрий Ярош (внесен в РФ в перечень террористов и экстремистов), ныне лидер праворадикального движения "Правый сектор", деятельность которого запрещена на территории России.
24 февраля 2014 г. после смены власти в результате событий "евромайдана" был назначен Верховной Радой председателем Службы безопасности Украины. 28 февраля 2014 г. вошел в состав Совета национальной безопасности и обороны Украины. В период его руководства СБУ спецподразделения службы принимали активное участие в вооруженном конфликте на юго-востоке Украины. 18 июня 2015 г. Верховная Рада отправила Валентина Наливайченко в отставку с поста председателя СБУ. "За" проголосовали 248 депутатов при 226 минимально необходимых.
19 декабря 2014 г. Следственный комитет России возбудил уголовное дело в отношении Наливайченко. Он подозревается в клевете, организации применения запрещенных средств и методов ведения войны, воспрепятствовании законной профессиональной деятельности журналиста и похищении человека.
С осени 2015 г. был председателем "Антикоррупционного движения".
В марте 2016 г. на базе "Антикоррупционного движения" и более 150 общественных организаций Украины основал партию "Общественно-политическое движение Валентина Наливайченко "Справедливость". Возглавлял ее до июня 2019 г.
На выборах президента Украины 31 марта 2019 г. занял 12-е место из 39, получив 0,22% голосов избирателей.
На внеочередных парламентских выборах 21 июля 2019 г. был избран народным депутатом Верховной рады IX созыва по списку партии "Батькивщина".
13 апреля 2022 г. Следственный комитет России возбудил в отношении Валентина Наливайченко уголовное дело по статье о призывах к насилию в отношении российских военных (п. "а", "б" ч. 2 ст. 282 УК РФ; возбуждение ненависти в отношении социальной группы военнослужащих, совершенное публично, сопряженное с угрозами применения насилия, лицом с использованием своего служебного положения). Следствием было установлено, что Наливайченко в эфире одного из украинских телеканалов высказал угрозы в адрес российских военнослужащих, принимающих участие в специальной военной операции на Украине.
В мае 2023 г. был внесен в РФ в перечень террористов и экстремистов.
В мае 2024 г. МВД России объявило Наливайченко в розыск. По какой именно статье ведется розыск, не уточнялось.
Государственный служащий первого ранга (2009).
Имеет ранг Чрезвычайного и Полномочного Посланника первого класса (2004).
Награжден орденом князя Ярослава Мудрого IV и V степеней.
Владеет английским, русским и финским языками.
Женат. Имеет дочь.