Kostenko holds a Ph.D from the Zaporizhia Institute of Engineering. In 1989, he became one of the founders of Rukh and has been a Member of the Verkhovna Rada (Parliament) since 1990 (except in 2006). In 2002 as a member of Our Ukraine. From 1992 to 1998 he served as the minister of environmental protection. Kostenko was a candidate at the Ukrainian presidential election, 1999 where he received 2.17% of votes. Kostenko was involved in Ukraine’s nuclear disarmament, which he later regretted, and in dealing with the aftermath of the Chernobyl disaster.
Before the parliamentary elections in 2006 Kostenko initiated the creation of a coalition known as Ukrainian National Bloc of Kostenko and Plyushch who has acquired 1.9% of the vote and did not exceed the 3% threshold of the election.
In July 2007 Kostenko and Ivan Plyushch joined together the block Our Ukraine–People's Self-Defense Bloc and both got re-elected as MP. Unlike many allies of Yushchenko, Kostenko did not defected from the Our Ukraine grouping in parliament.
Kostenko's Ukrainian People's Party competed on one single party under "umbrella" party Our Ukraine in the 2012 Ukrainian parliamentary election, together with Congress of Ukrainian Nationalists; this list won won 1.11% of the national votes and no constituencies and thus failed to win parliamentary representation. Kostenko was second the election list of Our Ukraine.
- Ukrainian People’s Party nominates its leader Kostenko for president, Interfax-Ukraine (October 24, 2009)
- Kostenko will pick up votes in west, but not in other regions, Kyiv Post (January 14, 2010)
- (Ukrainian) ЦВК оприлюднила офіційні результати 1-го туру виборів, Gazeta.ua (January 25, 2010)
- (Ukrainian) Proportional votes & Constituency seats, Central Election Commission of Ukraine
- (Ukrainian) "Наша Україна" хоче бути альтернативою усім учасникам виборів "Our Ukraine" wants to be an alternative to all election participants , BBC Ukrainian (31 July 2012)