The structure and magnetic properties of the two vacancy ordered double perovskites, K2ReBr6 and K2ReI6, are described. In room temeprature, K2ReBr6 has a cubic structure in space group Fm¯3m that transforms to a tetragonal structure described in P4/mnc below 290 K. Further cooling results in a second phase transition to a monoclinic structure in P21/n. The larger size of the iodide anion, compared to bromide, reduces the Goldschmidt tolerance factor and results in the monoclinic structure appearing at room temperature. The sequence of structures observed for K2ReBr6, Fm¯3m → P4/mnc → P21/n mirrors that of other 5d potassium hexabromides including K2OsBr6 and K2PtBr6 but is different than that seen for K2ReCl6. Unexpectedly, K2ReI6 undergoes a first-order transition from P21/n → Fm¯3m upon heating with both phases co-existing over a limited temperature range. K2ReI6 decomposes upon standing or heating, while K2ReBr6 remains stable in the laboratory for several months. Magnetic susceptibility measurements show both compounds undergo antiferromagnetic ordering at low temperatures and the Néel temperature, estimated from the magnetic susceptibility measurements, increases as the size of the halide increases; 8.2 K for K2ReCl6, 16.1 K for K2ReBr6, 26.9 K for K2ReI6.