Latem 2002 za 500 tysięcy euro Okoduwa przeniósł się do Arsenału Kijów. W swoim czwartym ligowym meczu dla Arsenału zdobył 2 gole w wygranym 8:1 meczu z Wołyniem Łuck. Łącznie w sezonie zagrał w 26 meczach zdobywając w nich 7 goli i zajmując ze swoim klubem 5. miejsce w tabeli. W sezonie 2003/2004 drużyna Arsenału zagrała gorzej jak w poprzednim i skończyła na 9. miejscu w tabeli. Dorobek Emmanuela w lidze to 21 meczów i tylko 2 zdobyte bramki. Rok później Arsenał znów zajął 9. miejsce, ale Okoduwa grał już skuteczniej i uzyskał 8 bramek w lidze. Błysk talentu Okoduwy nastąpił w sezonie 2005/2006, w którym to zdobył 15 z 31 ligowych bramek Arsenału i wraz z Brazylijczykiem z Szachtara, Brandão wywalczył tytuł króla strzelców ligi ukraińskiej. Bramki te znacznie przyczyniły się do obrony Arsenału przed spadkiem z ligi i zajął w niej bezpieczne 12. miejsce.