In this paper is described the preparation of new platinum-free Pd-Co carbon-nitride electrocatalysts (Pd-Co-CNs) for application in low-temperature fuel cells. Two groups of materials with formula Kn[PdxCoyCzNlHm] were synthesized, which are grouped in two ensembles: the first is characterized by a molar ratio y/x > 1 (I), and the second by y/x < 1 (II). Kn[PdxCoyCzNlHm] materials were prepared through a two-step synthesis protocol. The effect of the Pd/Co molar ratio and of the temperature of the thermal treatments on the structure and properties of the products were studied extensively by thermogravimetry, scanning electron microscopy, and vibrational (FT-IR and micro-Raman) and XPS spectroscopy. Vibrational studies revealed that I and II systems consist of two polymorphs of α- and graphitic-like carbon-nitride nanomaterials. The electrochemical activity towards the oxygen reduction reaction (ORR) and the hydrogen oxidation reaction (HOR) was measured by cyclic voltammetry measurements with thin-film rotating disk electrode (CV-TF-RDE). The electrochemical performance of Pd-Co-CNs of group I obtained at tf ≥ 700 °C resulted higher than that measured for a platinum-based commercial electrocatalyst in terms of both the activity towards the ORR and the HOR and of the resistance towards the poisoning effect of methanol towards the ORR.