Four new double perovskites, SrLaMReO6 (M = Mg, Mn, Co, Ni) in which Re5+ (5d2) is present, were prepared via conventional solid state reactions and characterized by X-ray and neutron powder diffraction, XANES, SQUID magnetometry, and muon spin relaxation (μSR). Synchrotron X-ray and neutron diffraction experiments confirmed that all compounds crystallize in the monoclinic P21/n structure type, which consists of alternately corner-shared octahedra of MO6 and ReO6. Rietveld refinement results indicated anti-site mixing of less than 7% on the M/Re sites. Bond valence sum calculations (BVS) suggest all M and Re ions are 2+ and 5+, respectively, and for the Mn-containing phase this is also supported by XANES measurements. All of the materials are paramagnetic at room-temperature and their Curie–Weiss temperatures are positive (except for Mg) indicating net ferromagnetic interactions. No evidence for long-range magnetic order is evident in the dc magnetic susceptibility and μSR measurements for SrLaMgReO6 to 2 K. The Mn-phase shows long-range order at TC = 190 K and neutron diffraction revealed a ferromagnetic structure with a refined net moment of ∼3.7μB. Both Co- and Ni-containing phases exhibit spin glass behavior at TG = 23 and 30 K, respectively, which is supported by neutron diffraction and a.c. susceptibility data. The structure and physical properties of these four new rhenium based ordered double perovskites are compared to the closely related “pillared perovskites”, La5Re3MO16, the isoelectronic Os6+ (5d2) double perovskite Sr2CoOsO6, and the Re6+ (5d1) double perovskites, Sr2MReO6, (M = Mg, Ca, Mn, Co, Ni).