29 maja 2006 otrzymał nominację na I wiceszefa Służby Bezpieczeństwa Ukrainy, kierował Centrum Antyterrorystycznym przy SBU. Od 6 grudnia 2006 do 6 marca 2009 pełnił obowiązki szefa SBU. 6 marca 2009 decyzją prezydenta Wiktora Juszczenki formalnie stanął na czele tej instytucji. Kierował nią do 11 marca 2010. Od kwietnia 2007 był również członkiem Rady Bezpieczeństwa Narodowego i Obrony Ukrainy.
W wyborach w 2012 wystartował z trzeciego miejsca na liście wyborczej partii UDAR Witalija Kłyczki, uzyskując mandat deputowanego VII kadencji. W wyniku wydarzeń Euromajdan skutkujących odsunięciem od władzy ekipy prezydenta Wiktora Janukowycza Wałentyn Naływajczenko 24 lutego 2014 został ponownie mianowany na szefa Służby Bezpieczeństwa Ukrainy. Odwołany został 18 czerwca 2015.
W 2019 był kandydatem w wyborach prezydenckich, otrzymał około 0,2% głosów. W tym samym roku uzyskał mandat posła IX kadencji z listy Batkiwszczyny.
Odznaczony Orderem Jarosława Mądrego V i IV stopnia. Wałentyn Naływajczenko jest żonaty, ma córkę.