The occurrence of segregation in highly dilute alloys under irradiation is an unusual phenomenon that has so far eluded theoretical explanation. The fact that solute atoms segregate in alloys that, according to thermodynamics, exhibit full solubility, has significant practical implications, as the formation of precipitates strongly affects physical and mechanical properties. Using ab initio calculations, we are able to explain the origin of radiation-induced rhenium segregation in dilute tungsten-rhenium alloys. The model treats rhenium atoms and vacancies in tungsten as components of a ternary alloy. The phase stability of ternary W-Re-Vac alloys is evaluated using a combination of Density Functional Theory (DFT) calculations, performed for more than 200 alloy structures, and cluster expansion (CE). The accuracy of CE parametrization is assessed against the DFT data, where the cross-validation error is found to be less than 4.2 meV/atom. The formation free energy of W-Re-Vac ternary alloys is evaluated as a function of temperature by means of quasi-canonical Monte Carlo simulations, using effective two, three and four-body cluster interaction parameters. In the low solute concentration range (< 5 at%Re), solute segregation is found in the form of Re atoms decorating vacancy clusters. These clusters remain stable over a broad temperature range from 800K to 1600K. At lower temperatures, simulations predict the formation of 30 to 50 at.% Re-rich precipitates. The origin of the anomalous vacancy-mediated segregation of Re atoms in W can be rationalized using ab initio data on binding energies as functions of Re to vacancy ratio as well as from the perspective of “chemical” effective pair-interaction between the rhenium atoms and vacancies. DFT analysis shows that binding energies can be as high as 1.5 eV if the rhenium to vacancy ratio is in the range from 2.4 to 6.6. Predictions derived from Monte Carlo simulations of Re precipitates are in surprisingly good agreement with experimental observations performed using Atom Probe Tomography of self-ion irradiated W-2at.% Re alloys, as well as with Transmission Electron Microscopy investigations of neutron-irradiated W samples containing up to 1.4 at.% Re.