Nanofiber-based La0.2Sr0.8TiO3−Gd0.2Ce0.8O1.9 (LST−GDC) composite anodes show good electrochemical performance and microstructure stability when subjected to reduction and oxidation (redox) cycling. With the increasing amount of GDC, the polarization resistance of LST−GDC composite anode gradually decreases. The porous LST nanofiber scaffold in the composite anode buffers the volume change caused by the transition between Ce4+ and Ce3+, which improves the LST−GDC electrode redox stability. A comparative study of the electrochemical performance of the composite anode has been conducted with 1 mol%CeO2-10 mol%Sc2O3-89 mol%ZrO2 (ScSZ), 8 mol% yttria stabilized zirconia (YSZ) and La0.8Sr0.2Ga0.8Mg0.2O3−δ (LSGM) electrolytes to evaluate the effects of electrolytes with different oxygen ion conductivity on anode interfacial polarization resistance. Among the three electrolytes, the LST−GDC composite anode with LSGM as the electrolyte shows the best electrochemical performance due to the electrolyte high O2− conductivity.