The decision is the latest episode in an ongoing struggle between pro-presidential and pro-premier factions in the country, which over the past six months has seen several ministers appointed by President Yushchenko and then dismissed by the Supreme Rada, where the pro-Russian Party of Regions, led by Prime Minister Viktor Yanukovych, holds a majority.
With 226 votes required for approval, only 196 Supreme Rada deputies voted in support of Volodymyr Ohryzko for the post of foreign minister, and 190 deputies in support of Viktor Korol for the post Ukrainian Security Service head.
Under Ukrainian law, the president has the right to propose both candidates to the parliament for a second time.
Ohryzko said that the majority of the parliament did not back his candidacy for political reasons.
"There were more political approaches rather than professional," he said.
A former deputy foreign minister, Ohryzko, 50, has been acting foreign minister since the January 31 resignation of Boris Tarasyuk, a key presidential ally who actively promoted pro-Western policy goals during his time in office.
On January 1, 2006, Ukraine shifted from a presidential-parliamentary to a parliamentary-presidential form of governance, after amendments adopted by the Supreme Rada in December 2004 came into force.
As a result, some presidential powers were transferred to the country's parliament and to the Cabinet.
