A fuel cell electrode catalyst including an active complex including a cerium (Ce)-nitrogen (N) bond and having an oxygen reduction activity. Also, a method of preparing a fuel cell electrode catalyst, the method including providing a pre-catalyst including a pre-active complex having a cerium-oxygen bond; and thermally treating the pre-catalyst in the presence of a nitrogen-containing material at a temperature of from about 700° C. to about 2000° C. to prepare the electrode catalyst, the electrode catalyst including an active complex comprising a cerium-nitrogen bond. Also a fuel cell membrane-electrode assembly, the membrane-electrode assembly including: a cathode; an anode disposed opposite to the cathode; and an electrolyte membrane disposed between the cathode and the anode, at least one of the anode and the cathode including the fuel cell electrode catalyst.