В 1984-1986 годах Наливайченко служил в рядах Советской армии [33]. Сообщалось, что перед уходом в армию он начал учиться в Харьковском государственном университете по специальности "преподавание русского языка как иностранного", однако в результате призыва учебу пришлось прервать [21].
В 1990 году [33] Наливайченко c отличием окончил Киевский национальный университет имени Тараса Шевченко, получив филологическое образование [23] (по другим данным - философское [25]). В дальнейшем в прессе он упоминался как "филолог, референт-переводчик, специалист по международным отношениям" [32].
После окончания вуза Наливайченко устроился на работу в Киевский инженерно-строительный институт преподавателем русского языка иностранным студентам. Он был назначен заведующим отдела по работе с иностранцами. Там же ему предложили продолжить образование, но уже по линии спецслужб. Наливайченко был направлен на учебу в Краснознаменный имени Ю.В.Андропова институт КГБ СССР (позднее он был переименован в Академию внешней разведки). Однако разведчиком Наливайченко не стал. К моменту его возвращения КГБ Украины находился "на этапе развала" и тогда он ушел из органов [19].
О деятельности Наливайченко в начале 1990-х годов известно мало. По некоторым данным, он работал по специальности - занимался преподаванием и переводами [21], а также был сотрудником запорожского частного предприятия "Качество" [23], где "занимался маркетингом" [21].
С мая 1994 года по ноябрь 1997 года Наливайченко был вторым и первым секретарем Посольства Украины в Финляндии, по совместительству - в Дании и Норвегии [33], [23].
В 1997 году Наливайченко стал сотрудником консульского управления МИД Украины. До мая 2001 года он последовательно занимал должности первого секретаря, советника, заведующего отделом и заместителя начальника управления [33], [23].
В 2001 году Наливайченко был назначен генеральным консулом посольства Украины в США [31], [23].
В ноябре 2003 года Наливайченко занял пост директора департамента консульской службы МИД Украины [31], [23].
В феврале 2004 года Наливайченко был назначен на должность заместителя министра иностранных дел Украины [31], [23]. В этом качестве Наливайченко был членом комиссии при президенте Украины по вопросам гражданства, а также возглавил делегацию Украины на переговорах с Еврокомиссией о подписании Соглашения о реадмиссии [23], [32].
30 декабря 2005 года указом президента Виктора Ющенко Наливайченко был
назначен Чрезвычайным и Полномочным Послом Украины в Республике Беларусь, а в феврале 2006 года освобожден от обязанностей замминистра иностранных дел. Верительные грамоты президенту Белоруссии Александру Лукашенко
Наливайченко вручил в марте 2006 года [31], [23], [33].
29 мая 2006 года Наливайченко занял пост первого зампредседателя Службы безопасности Украины (СБУ), что для многих стало неожиданностью [23], [30]. В декабре 2006 года Наливайченко был назначен исполняющим обязанности председателя СБУ [29]. После этого назначения стала появляться информация о том, что кроме дипломатии Наливайченко "был всю жизнь связан со спецслужбами". В частности, глава Секретариата президента Украины Виктор Балога сразу после
назначения назвал его "опытным разведчиком и дипломатом" [29], а депутат от БЮТ Андрей Кожемякин даже заявлял журналистам, что Наливайченко "окончил
школу КГБ" [21].
По мнению ряда наблюдателей, за то время, пока спецслужбой в качестве и.о. руководил Наливайченко, она "оказалась втянута в политическое противостояние между президентом и правящей коалицией", завершившееся итоге роспуском Верховной Рады пятого созыва [21], [22]. Отмечалось, что как исполняющий обязанности главы СБУ Наливайченко неоднократно делал сенсационные заявления. Среди них - обвинения в коррупции судьи Конституционного суда Украины Сюзанны Станик (именно ей была отведена роль докладчика по делу о конституционности указа Ющенко о роспуске парламента) [27], [23], а также оглашение информации о возможной угрозе безопасности лидера блока БЮТ Юлии Тимошенко [28] и рассказ о задержании бывшего министра транспорта и связи Николая Рудьковского [20]. В связи с этим звучали обвинения Наливайченко не только в "самопиаре", но и в использовании Службы безопасности в политических целях. Пресса, имея в виду Наливайченко, с иронией отмечала присущее руководству украинских спецслужб "стремление поделиться самым сокровенным с благодарной публикой", которое практически всегда совпадало "с очередными обострениями внутриполитической ситуации" [24]. По словам члена фракции Партии регионов Владимира Сивковича, сотрудники СБУ даже прозвали своего шефа Заливайченко [26].
21 октября 2008 года газета "Известия" опубликовала интервью с Наливайченко, в котором, отвечая на вопрос о запрете на въезд некоторых российских граждан, глава СБУ обвинил депутата Государственной думы РФ Константина Затулина в нарушении закона о правовом статусе иностранца. При этом он утверждал, что данный факт был неоднократно доказан СБУ в суде [18]. Затулин 28 октября 2008 года отверг все обвинения в свой адрес, заявив, что "представители СБУ в судебном заседании были вынуждены подтвердить, что я никогда не нарушал ни украинское, ни международное законодательство и, по сути, был ограничен в правах из 'профилактических соображений'" [17]. 9 февраля 2009 года Тверской суд Москвы признал несоответствующими действительности заявления Наливайченко относительно того, что СБУ дважды доказывало в украинском суде факты противоправных действий Затулина на территории Украины. В качестве компенсации суд взыскал с Наливайченко 300 тысяч рублей [16].
Президент Ющенко неоднократно с 2007 года вносил в Верховную Раду Украины представления о назначении Наливайченко председателем Службы безопасности Украины, однако к началу 2009 года он так и не был утвержден в этой должности [30], [22], [16]. Главой СБУ парламент утвердил Наливайченко только 6 марта 2009 года. При этом отмечалось, что кандидатуру нового председателя Службы не поддержали лишь Партия регионов и Коммунистическая партия Украины (КПУ) [13], [14].
Однако вскоре после произошедшего депутаты из фракции "Наша Украина — Народная самооборона" обвинили депутатов от БЮТ - своих соратников по парламентской коалиции - в непоследовательности и даже предположили, что кандидатура Наливайченко "была согласована с руководством Блока Тимошенко путем шантажа". После этого представители БЮТ объявили решение о поддержке кандидатуры Наливайченко ошибочным и предложили парламентариям направить президенту Украины представление с требованием освободить Наливайченко от должности председателя СБУ [15], [12]. Но этого не произошло. В том же месяце президент Ющенко подписал указы об освобождении Наливайченко от должности первого заместителя председателя СБУ – руководителя Антитеррористического центра [11] и утвердил его в качестве члена Совета национальной безопасности и обороны (СНБО) Украины [10].
После прихода к власти президента Виктора Януковича [9] 1 марта 2010 года Наливайченко ушел в отпуск [8], а 11 марта постановлением парламента был освобожден от должности председателя СБУ [7].
В сентябре того же года Наливайченко был избран главой политического совета и фактическим лидером партии "Наша Украина" (почетный председатель - Виктор Ющенко) [6]. 24 мая 2012 года Наливайченко ушел с поста председателя политсовета партии и отказался от членства в "Нашей Украине". Свой выход из партии он объяснил тем, что "Наша Украина" затягивала процесс вступления в объединенную оппозицию перед очередными парламентскими выборами [5].
26 июля 2012 года стало известно, что Наливайченко присоединился к партии"УДАР" Виталия Кличко [4]. В партийный список УДАРа на выборах в
Верховную Раду седьмого созыва, намеченных на 28 октября того же года, Наливайченко был включен под третьим номером [3]. По итогам выборов УДАР занял третье место, получил, по данным подсчета более чем 99,95 процента бюллетеней, 14 процентов голосов, в то время как Партия регионов - 30 процентов, а объединенная оппозиция на основе Батькивщины - 25,5 процента [2], [1].