La0.98Cr0.75Mn0.25O3−δ–Ce0.9Gd0.1O1.95 (LCM-CGO) nanocomposite layers with different LCM contents, between 40 and 60 wt %, are prepared in a single step by a spray-pyrolysis deposition method and evaluated as both air and fuel electrodes for solid oxide fuel cells (SOFCs). The formation of fluorite (CGO) and perovskite (LCM) phases in the nanocomposite electrode is confirmed by different structural and microstructural techniques. The intimate mixture of LCM and CGO phases inhibits the grain growth, retaining the nanoscale microstructure even after annealing at 1000 °C with a grain size lower than 50 nm for LCM-CGO compared to 200 nm for pure LCM. The synergetic effect of nanosized LCM and CGO by combining their high electronic and ionic conductivity, respectively, leads to efficient and durable symmetrical electrodes. The best electrochemical properties are found for 50 wt % LCM-CGO, showing polarization resistance values of 0.29 and 0.09 Ω cm2 at 750 °C in air and H2, respectively, compared to 2.05 and 1.9 Ω cm2 for a screen-printed electrode with the same composition. This outstanding performance is mainly ascribed to the nanoscale electrode microstructure formed directly on the electrolyte at a relatively low temperature. These results reveal that the combination of different immiscible phases with different crystal structures and electrochemical properties could be a promising strategy to design highly efficient and durable air and fuel electrodes for SOFCs