Cathodes compatible with Ca-doped LaNbO4 (LCNO) and the operation of a complete proton conducting fuel cell based on this electrolyte are presented. The best performing cathode was a 50 vol.% La0.8Sr0.2MnO3 (LSM)–50 vol.% LCNO composite, with an overall area specific resistance (ASR) of ~ 10 Ω cm2 at 800 °C in wet air. Pt and La0.8Sr0.2(Cr0.5Mn0.5)O3-based cathodes exhibit higher ASRs. The performance of a complete Ni–LCNO//LCNO//LSM–LCNO fuel cell shows a high open circuit voltage but with relatively low performance, in agreement with the modest proton conductivity of LaNbO4-based materials and cathode performances. The cell exhibits stable operation with CO2 containing atmosphere on the cathode side, confirming the chemical robustness of LaNbO4-based electrolytes.