The development of new catalysts for high-performance, cost-effective oxygen reduction is crucial in the commercialization of fuel cells. We demonstrate here the use of functionalized polyterthiophene-anchored graphene oxide (GO) composites as new non-metal catalysts for the oxygen reduction reaction. Different functional groups containing the monomers 3′-(2-aminopyrimidyl)-2,2′:5′,2′′-terthiophene (APT), 3′-(p-benzoic acid)-2,2′:5′,2′′-terthiophene (TBA) and 3′-(carboxylic acid)-2,2′:5′,2′′-terthiophene (TCA) were synthesized and polymerized with as-prepared GO to form complexes by a potential cycling method. The aminopyrimidyl groups on the poly(APT) backbone served as effective functional groups in the oxygen reduction reaction. The APT-GO complex was formed through hydrogen bonding and a ring-opening reaction of the epoxide group with the amine to form a new C-N bond. It was observed that the C-N bond in the polymer matrix was involved in the direct electrocatalytic reduction of O2 to H2O. The poly(APT-GO) composite showed much better tolerance to fuel cross-over and long-term electrode stability than commercially available Pt/C electrodes.