We report composition dependent structure evolution from SrTiO3 to SrFe0.5Ta0.5O3 by powder X-ray and neutron diffraction studies of SrTi1-2xFexTaxO3 (0.00 ≤ × ≤ 0.50) compositions. Structural studies reveal cubic (Pm3m) perovskite-type structure of the parent SrTiO3 for x up to 0.075 and cation disordered orthorhombic (Pbnm) perovskite-type structure for x ≥ 0.33. A biphasic region consisting of a mixture of cubic and orthorhombic structures is found in the range for 0.10 ≤ × ≤ 0.25. Dielectric studies reveal transformation from a normal dielectric to relaxor like properties with increasing Fe(3+) and Ta(5+) concentration. Dielectric response is maximum at x = 0.33 in the series. The results establish a protocol for designing new lead-free relaxor materials based on the co-substitution of Fe(3+) and Ta(5+) for Ti(4+) in SrTiO3. A complex interplay of strain effects arising from distribution of cations at the octahedral sites of the perovskite structure controls the dielectric properties.