Polycrystalline Sr2FeMoO6 samples are synthesized by an encapsulation technique under very low oxygen partial pressures utilizing the Fe/FeO redox couple as an oxygen getter. A route based on thermal decomposition of metal complexes, using ethylenediaminetetraacetic acid as the complexant, is developed to prepare a precursor powder. Single-phase samples are readily obtained even at temperatures as low as 900 °C. The degree of Fe/Mo ordering and the grain size are well-controlled by sintering temperature and time. Homogeneous morphology of the samples is confirmed from scanning electron microscopy images. Rietveld refinements of X-ray diffraction patterns indicate that the degree of order (S) at the Fe/Mo sites is higher than 0.95 for samples sintered at 1150 °C for 100 h. For the same sample a record-high saturation magnetization of 3.96 μB, which is very close to the theoretical value of 4 μB, is obtained. It is considered that the high degree of order stems from the uniform mixing of starting reactants in an atomic scale and also from the stability of overall cation stoichiometry during sample sintering in an encapsulated ampule. It is found that the Curie temperature exhibits a nonmonotonic dependence on S, with the maximum at S ≈ 0.84. Additionally, evidence for super-paramagnetic-type behavior in the present solution-derived samples is obtained from the Mössbauer data.