The development of sulfur-tolerant anode materials is vital for solid-oxide fuel cells (SOFCs) that use conventional fossil fuels as fuel source to decrease emissions and increase energy-conversion efficiency. In this work, A2CrMoO6–δ (A = Ca, Sr, Ba) double perovskite materials are synthesized and evaluated as potential SOFC anode materials to assess their electrocatalytic activity and sulfur tolerance. All samples exhibit well-matched thermal expansion coefficient and satisfactory chemical compatibility with La0.9Sr0.1Ga0.8Mg0.2O3–δ (LSGM) electrolyte over the measured temperature range. Among the compositions investigated, the B-site partially disordered Sr2CrMoO6–δ (SCM) double perovskite exhibits superior electrical conductivity, cycle stability, and polarization resistance on LSGM electrolyte because of its high-symmetry structure and appropriate oxygen-vacancy concentration. The relatively stable single-cell performance in 100 ppm H2S/H2 demonstrates that the behavior of SCM anode is more stable than that of nickel–yttria-stabilized zirconia. Postexposure characterization by X-ray diffraction is further conducted to evaluate SCM as potential sulfur-tolerant SOFC anode.