Two series of compositions, BaCe0.8-xGd0.2RuxO3-δ (BCGRx, x=0-0.8) and BaGd1-yRuyO3-δ (BGRy, y=0.5-1.0), were synthesized and their crystal phases were examined. The BCGR0.15 and BGR0.5 oxides were a single phase of perovskite solid solution, while BCGR0.67 and BGR0.67 were a perovskite-related superstructure phase. The onset voltage (Vo) of the reduction current and the efficiency (E4) of the 4-electron reduction of oxygen were evaluated by semi-steady state voltammetry with rotating ring-disk electrodes. In the BCGRx series, the activities for electrochemical oxygen reduction (EOR) increased with increasing Ru content. In the BGRy series, the BGR0.67 superstructure phase showed a higher EOR activity than the perovskite BGR0.5 and the hexagonal(4H) BaRuO3. This indicates that the EOR activity depends on the crystal phase. The BGR0.67 exhibited the best EOR activity of all the samples. The Vo value was 0.80 V vs. reversible hydrogen electrode and the E4 value was almost 100 %.