Дипломатическая карьера. Данные о том, чем занимался Наливайченко в начале 1990-х, в его автобиографии почему-то отсутствуют. По крайней мере, как сообщала газета Сегодня со ссылкой на источники в СБУ, в 1994-м он был сотрудником запорожского частного предприятия Качество.

Большая же часть карьеры Наливайченко связана с работой дипломатом, на которой он дослужился до ранга чрезвычайного и полномочного посланника первого класса. В 1994-1997 гг. работал вторым, первым секретарем посольства Украины в Финляндии, по совместительству – в Дании и Норвегии. Затем до мая 2001-го – первым секретарем, советником, заведующим отделом, заместителем начальника консульского управления МИД Украины. Следующие два года – генеральным консулом посольства Украины в США. С ноября 2003-го по февраль 2004-го – директором департамента консульской службы МИД Украины. Очередной этап (до февраля 2006-го) – пост заместителя министра иностранных дел Украины. В это время Наливайченко довелось быть членом комиссии при президенте Украины по вопросам гражданства, главой делегации Украины на переговорах с Еврокомиссией о подписании соглашения о реадмиссии.

Еще будучи на посту замминистра, 30 декабря 2005 года, Наливайченко указом президента Виктора Ющенко был назначен чрезвычайным и полномочным послом Украины в Республике Беларусь. Верительные грамоты президенту Беларуси Александру Лукашенко вручил 13 марта 2006 года.

Из дипломатов – в СБУ. 29 мая того же 2006-го неожиданно для многих глава государства пересадил Наливайченко в кресло первого зампредседателя Службы безопасности Украины. Спустя полгода, 22 декабря, президент увольняет главу СБУ Игоря Дрижчаного. Хотя тот еще в августе, во время формирования нового Кабмина и глобальных кадровых перестановок в других ключевых органах власти, по мнению наблюдателей, вполне устраивал на своем посту команду главы государства, поскольку считался вполне контролируемым и предсказуемым. С момента отставки Дрижчаного функции главы СБУ с приставкой “и.о.” выполняет Наливайченко. За это время спецслужба не только выполняла обычные, присущие ей функции, но и оказалась втянута в политическое противостояние между президентом и правящей коалицией в составе Партии регионов, Соцпартии и КПУ. В первой половине 2007 года СБУ и фамилия Наливайченко неоднократно упоминались в комментариях политиков, экспертов и сообщениях СМИ сперва в контексте войны полномочий между Ющенко и премьером Виктором Януковичем, затем – в рамках обострения политического кризиса, разразившегося роспуском Верховной Рады V созыва.

На руководство СБУ со стороны оппонентов Ющенко и оппозиции обрушился шквал обвинений в том, что служба занялась обслуживанием интересов Секретариата президента и политическими репрессиями. Особенно громкой критика стала после резонансного заявления Наливайченко о том, что у его ведомства появились основания подозревать в получении крупной взятки судью Конституционного Суда Сюзанну Станик, которой была отведена роль докладчика по делу о конституционности указа президента о роспуске парламента. Одним из наиболее ярых критиков СБУ и лично Наливайченко в те дни оказался член фракции Партии регионов Владимир Сивкович. Он даже предположил, что шеф СБУ за свои высказывания вполне может угодить за решетку. “У него сейчас среди сотрудников даже кличка появилась – не Наливайченко, а “Заливайченко”, потому что его поведение в такой структуре, как СБУ, воспринимается очень отрицательно”, – тогда же сказал политик-регионал.

Тем не менее, прогноз Сивковича не сбылся. Впрочем, довольно комфортно в должности и.о. шефа Службы безопасности Наливайченко чувствовал себя и год спустя. А в попытках преследования по политическим мотивам СБУ стали периодически обвинять не регионалы или коммунисты, а недавние союзники президента – члены Народной самообороны и Блока Юлии Тимошенко.

6 марта 2009 года Верховная Рада Украины 230 голосами одобрила назначение Наливайченко председателем СБУ (без приставки “и.о.”). В марте 2010 года, после прихода к власти Виктора Януковича, был уволен. Его место занял Валерий Хорошковский.

24 февраля 2014 г. Верховная Рада назначила Наливайченко на должность главы СБУ, предварительно уволив Александра Якименко.

18 июня 2015 года Верховная Рада поддержала отставку Валентина Наливайченко с должности главы Службы безопасности Украины. За соответствующее постановление №2110а проголосовали 248 народных депутатов.

Партийная деятельность. Несколько лет возглавлял политсовет партии Наша Украина. Занял этот пост после Веры Ульянченко. В мае 2012 года сложил полномочия в руководящем органе Нашей Украины и вышел из партии.

С декабря 2012 года – народный депутат Украины VII созыва, в парламент прошел под №3 списка партии УДАР. Первый замглавы комитета ВР по иностранным делам. Член партии УДАР. На момент избрания числился руководителем группы советников ООО Смайл Холдинг Украина.
Во время депутатской деятельности в Верховной Раде, одним из двадцати помощников-консультантов Валентина Наливайченко с 1 апреля 2013 года по 25 февраля 2014 был Дмитрий Ярош, с которым их связывают многолетние дружеские отношения. Поддерживает Наливайченко и возглавляемую Ярошем организацию “Тризуб”.

Регалии. Чрезвычайный и полномочный посланник 1-го класса (2004), государственный служащий 3-го ранга (2006), 2-го ранга (2007), 1-го ранга (2009). Награжден орденом Ярослава Мудрого V ст. (2007), орден Ярослава Мудрого ІV ст. (2010), командор ордена “За заслуги перед Литвой” (2009).