AxSr1−x(Fe0.5Ru0.5)O3 double perovskites (x = 0.05 and A = Ba,Ca) were prepared by a sol-gel method and an effect of the cation substitution at the A site of the crystal structure of SrFe0.5Ru0.5O3 on their magnetic properties was monitored by x-ray diffraction (XRD), magnetic measurements, transmission electron microscopy (TEM), scanning electron microscopy (SEM), and temperature-dependent and in-field 57Fe Mössbauer spectroscopy. Both Ca- and Ba-substituted samples reveal the orthorhombic structure similar to the undoped perovskite; however, the cell volume changes with the substituting ion radius. TEM and SEM micrographs manifest agglomerated nanocrystalline samples with particle sizes of about 20–60, 15–50, and 40–70 nm for the undoped, Ba-doped, and Ca-doped perovskites, respectively. Generally, the magnetic regime of both substituted and undoped perovskites can be described by a spin-glass behavior caused by a spin frustration. Among other factors, this is manifested by a nonsaturation of the hysteresis loops even at a high field of 50 kOe, by a low-temperature divergence of the zero-field-cooled and field-cooled magnetization curves, and by a cusp in the zero-field-cooled magnetization curve. The low-temperature spin-glass state is also supported by the in-field Mössbauer spectra, recorded on these systems. The isomer shift parameters, extracted from the Mössbauer spectra, confirm a high-spin iron(III) state with S = 5/2. In contrast to the undoped and Ba-doped samples, the narrower distribution of the hyperfine magnetic fields, observed in the Ca-doped perovskite can be ascribed to the larger particles. Compared to the undoped sample, the field of maximum probability is higher in the Ca-substituted perovskite while it is reduced in the Ba-doped sample because of the effects of the chemical compression and expansion, respectively. In addition, the Ca-doped sample exhibits more negative Weiss temperature (Θ = −105 K) than that found for the Ba-substituted perovskite (Θ = −49 K), implying that doping with Ca at Sr sites of SrFe0.5Ru0.5O3 perovskite structure provokes strengthening of antiferromagnetic interactions at the expense of the other ones. Furthermore, both substituted samples reveal significantly reduced coercive fields in the hysteresis loops recorded at 5 K, probably as a result of decreasing magnetocrystalline anisotropy. This is an indirect evidence of the essential influence of the substitution on the crystal growth of the synthesized particles. The role of SrRuO3 and SrFeO3 compounds, which have been detected in magnetic and Mössbauer measurements as admixtures, is discussed.