Народився 3 січня 1959 р. у с. Піски Баштанського району Миколаївської області у сім’ї робітників. У 1968 р. уся сім’я переїхала до селища станції Маніхіно Істрінського району Московської області (Росія) через хворобу батька, яка вимагала зміни клімату. Проте Навоєнки довго там не затрималися, адже прагнули жити в Україні. Уже в 1971 р. повернулися на Батьківщину й оселилися в мальовничому селищі Немішаєве Бородянського району Київської області.

У 1976 р. Віктор Олександрович закінчив Немішаївську середню загальноосвітню трудову політехнічну школу, де здобув першу робітничу професію (слюсаря). Дуже любив читати. Захоплення пригодницькими та історичними романами у дитинстві згодом переросло в справжню пристрасть до художнього слова, яку, вже ставши батьком, передав і своїм дітям, виховуючи їх на найкращих зразках класичної літератури. Мав легку й веселу вдачу, гострий розум і тонке почуття гумору. Завжди був душею компанії, міг підтримати будь-яку розмову. Займався спортом. З 1976 по 1977 р. працював слюсарем з ремонту автомобілів І розряду. У 1977 р. був призваний на службу до Радянської Армії, яку проходив у Азербайджані до 1979 р. у складі військ протиповітряної оборони.

Після армії В. О. Навоєнко спробував вступити до Київського інс­титуту народного господарства імені Д. С. Коротченка, але, щоб пройти конкурс, не вистачило півбала, тож пішов навчатися у Київське міське професійно-технічне училище № 1, де отримав кваліфікацію слюсаря механоскладальних робіт ІІІ розряду з відзнакою. В 1980 р., після закінчення училища, працював на Немішаївському заводі біохімічних препаратів слюсарем з ремонту автомобілів. Цього ж року нареш­ті став студентом омріяного КІНГ ім. Д. С. Коротченка, вступивши на факультет економіки і планування матеріально-технічного постачання (спеціальність «Економіка і планування матеріально-технічного постачання»). Віктор Олександрович мав активну життєву позицію. Під час навчання брав участь у студентському самоврядуванні, працював у студентських будівельних загонах. Викладацька спільнота знала його як надзвичайно ініціативного й працьовитого студента, а одногрупники — як вірного друга й мудрого порадника.

З 1986 по 2001 р. В. О. Навоєнко працював у органах внутрішніх справ України Головного управління Міністерства внутрішніх справ України в Київській області. У перший же рік служби долучився до ліквідації наслідків катастрофи на Чорнобильській АЕС. Переважно на плечі правоохоронців Київської області лягла грандіозна за масштабами операція з відселення людей за межі зони ураження в найкоротший термін. У ті важкі роки вся родина Віктора Олександровича не лишилася осторонь страшної трагедії і прийняла у своєму домі переселенців з Чорнобиля. Лейтенант В. О. Навоєнко разом із командою також відповідали за знищення одягу, техніки, харчових продуктів і будь-яких інших речей, які зазнали радіоактивного опромінення. Ті страшні «робочі будні», коли після закінчення зміни необхідно було знищити навіть свій просотаний радіацією одяг, залишили не лише болючі спогади на все життя, а й завдали непоправної шкоди здоров’ю Віктора Олександровича.

За 15 років самовідданої служби у внутрішніх органах Віктор Олександрович не раз ризикував життям, з честю й гідністю виконуючи свій службовий обов’язок, за що був відзначений державними нагородами: 2006 р. — пам’ятною відзнакою МВС України «20 років Чорнобильської катастрофи»; 2009 р. — пам’ятною відзнакою МВС України — медаллю «90 років карному розшуку України»; 2010 р. — відзнакою МВС України «За доблесть і відвагу в службі карного розшуку» II ступеня; 2012 р. — нагрудним знаком «Гідність та честь»; 2013 р. — орденом «Честь та Пошана» Всеукраїнської громадської організації інвалідів «Союз Чорнобиль України»; 2014 р. — почесною відзнакою — орденом «Учаснику ліквідації. Чорнобиль».

У відставку В. О. Навоєнко пішов за вислугою років.

З 2005 р. працював в ЗАТ «Кисневий завод» у відділі продажу і маркетингу, а згодом почав власну справу, пов’язану з киснем. Так з’явилося ПП «AIR».

15 лютого 2015 р. зупинилося серце Віктора Олександровича, не витримавши тягаря набутих за період ліквідації наслідків Чорнобильської катастрофи хвороб.

Завжди життєрадісний і дотепний, мудрий і розуміючий, наполегливий і витривалий В. О. Навоєнко прагнув допомагати людям і бути потрібним. Він і досі живе у пам’яті люблячої дружини, у твердому характері його дітей, у хитрому вогнику очей онуків.