Development of chemically stable proton conductors for solid oxide fuel cells (SOFCs) will solve several issues, including cost associated with expensive inter-connectors, and long-term durability. Best known Y-doped BaCeO3 (YBC) proton conductors-based SOFCs suffer from chemical stability under SOFC by-products including CO2 and H2O. Here, for the first time, we report novel perovskite-type Ba0.5Sr0.5Ce0.6Zr0.2Gd0.1Y0.1O3-δ by substituting Sr for Ba and co-substituting Gd + Zr for Ce in YBC that showed excellent chemical stability under SOFC by-products (e.g., CO2 and H2O) and retained a high proton conductivity, key properties which were lacking since the discovery of YBCs. In situ and ex- situ powder X-ray diffraction and thermo-gravimetric analysis demonstrate superior structural stability of investigated perovskite under SOFC by-products. The electrical measurements reveal pure proton conductivity, as confirmed by an open circuit potential of 1.15 V for H2-air cell at 700°C, and merits as electrolyte for H-SOFCs.