Novel high- and medium-entropy SrFe_1-xMo_xO_3-δ-based transition metal-doped perovskites are  synthesized for the first time, and assessed as potential electrode materials for both conventional and symmetrical Solid Oxide Fuel Cells (SOFC). Four compositions: SrFe_0.8Mo_0.2O_3-δ (SFM), SrFe_0.6Mo_0.2Co_0.2O_3-δ (SFMC), SrFe_0.4Mo_0.2Co_0.2Mn_0.2O_3-δ (SFMCM), and SrFe_0.2Mo_0.2Co_0.2Mn_0.2Ti_0.2O_3-δ (SFMCMT) are obtained by a solid-state synthesis method. For all materials, the structural analysis, with the use of XRD and SEM measurements, confirms presence of the single-phase structure. The oxygen nonstoichiometry level determination shows very interesting behavior, which is especially visible for the high-entropy SFMCMT composition, strongly deviating for prediction of the rule-of-mixtures. To assess the potential of those materials regarding symmetric-type operation (both as cathode and anode), their structural evolution under reducing conditions is studied, indicating a degree of either  exsolution or decomposition for all compositions. In the first case, such behavior should, at least in theory, enhance the catalytic properties of the materials under a reducing atmosphere. Most importantly, the analysis of the SFMCMT sample upon further reoxidation indicates at least partially reversible exsolution of the catalytically active Co- and Fe-rich metallic precipitates. The confirmed reversibility is a highly beneficial feature in terms of application in symmetrical SOFCs, indicating that the single-phase structure can be restored after reversing the polarization direction of the operating cell. The functional properties of all materials, including electrical conductivity, thermomechanical properties, and chemical stability toward the most common solid electrolyte materials, is studied. The selection of the B-site elements appears to have a prominent impact on the transport properties, in terms of the conductivity values, and the general character of its temperature dependence. The thermomechanical measurements indicate that the high-entropy approach leads to a significant decrease in the thermal expansion coefficient, with the recorded TEC for the SFMCMT equal to 13.1·10^-6 K^-1 and 15.1·10^-6 K^-1, below and above 500 °C, respectively. Such behavior is highly desired from the point of view of compatibility with other elements of the fuel cell, as the obtained values are closely matching the ones of typical electrolytes. Consequently, the SFMCMT is selected for further evaluation of the electrochemical performance, under both oxidizing and reducing conditions. The electrochemical impedance spectroscopy measurements prove that cathodic polarization resistance values for SFMCMT material are significantly lower than those for the conventional SFM material, obtained in the same experimental conditions. Overall, the high-entropy SFMCMT perovskite demonstrates a significant improvement in performance over the legacy SFM composition, making it a highly promising alternative for application in conventional and symmetrical SOFCs.