Jako mer Kijowa wystartował w wyborach prezydenckich w 2004, uzyskując w pierwszej turze około 0,5% głosów (8. miejsce z 24 kandydatów). Mimo iż Ołeksandra Omelczenkę uważano za osobę związaną z dotychczasową władzą, już drugiego dnia pomarańczowej rewolucji przeszedł na stronę opozycji, udzielając poparcia Wiktorowi Juszczence. Decyzja ta miała istotne znaczenie dla koordynacji akcji protestacyjnej (władze Kijowa przekazały uczestnikom protestu swoją siedzibę w centrum miasta, nakazały też służbom miejskim zająć się udzielaniem pomocy). Decyzja Ołeksandra Omelczenki przyczyniła się też do postawy dowódców kijowskiej milicji, którzy nieoficjalnie zapewnili przywódców opozycji, że nie użyją siły przeciwko demonstrantom. Mimo wsparcia ze strony Bloku Nasza Ukraina nie został ponownie wybrany na urząd mera w wyborach w 2006. Nowym merem Kijowa został Łeonid Czernowecki, także należący do stronników Wiktora Juszczenki w 2004, a jednocześnie będący jednym z głównych przeciwników Ołeksandra Omelczenki.