We present a comprehensive study of binary molybdenum alloy systems with low contents (1-4 at.%) of immiscible alloying elements such as sodium, yttrium and ytterbium. The alloys have been produced by use of high-energy ball milling under argon atmosphere for several hours. Further, the samples were annealed at different temperatures to stabilize different grain sizes. To characterize the as-milled and the annealed powder energy-dispersive x-ray analysis, x-ray diffraction experiments, transmission electron microscopy and atom-probe tomography have been performed. Thereby, we are able to investigate the relation between lattice parameter, grain size and solute content in dependence of both milling time and annealing temperature. In order to explain the experimental results, density functional theory calculations of some of the systems have been carried out to clarify the actual size of the solute atoms inside the molybdenum crystal lattice.