The development of highly efficient catalysts in the cathodes of rechargeable Li-O-2 batteries is a considerable challenge. Polyelemental catalysts consisting of two or more kinds of hybridized catalysts are particularly interesting because the combination of the electrochemical properties of each catalyst component can significantly facilitate oxygen evolution and oxygen reduction reactions. Despite the recent advances that have been made in this field, the number of elements in the catalysts has been largely limited to two metals. In this study, we demonstrate the electrochemical behavior of Li-O-2 batteries containing a wide range of catalytic element combinations. Fourteen different combinations with single, binary, ternary, and quaternary combinations of Pt, Pd, Au, and Ru were prepared on carbon nanofibers (CNFs) via a joule heating route. Importantly, the Li-O-2 battery performance could be significantly improved when using a polyelemental catalyst with four elements. The cathode containing quaternary nanoparticles (Pt-Pd-Au-Ru) exhibited a reduced overpotential (0.45 V) and a high discharge capacity based on total cathode weight at 9130 mAh g(-1), which was similar to 3 times higher than that of the pristine CNF electrode. This superior electrochemical performance is be attributed to an increased catalytic activity associated with an enhanced O-2 adsorbability by the quaternary nanoparticles.