Severe plastic deformation is known for its potential to obtain non-equilibrium solid solutions of metals, which under normal conditions are immiscible or have limited solubility. An important role in this process is played by the increased density of defects, which facilitates diffusion in the material during deformation. In particular, recently it was found that the application of ultra-severe plastic deformation can lead to dissolution of Zr atoms in aluminum, while the equilibrium phase diagram of these two metals shows that solid solution of Zr in Al is impossible. In the present work, we use molecular dynamics simulation to calculate the dependence of the lattice parameter of the Al-Zr solid solution as a function of the Zr concentration in the range from one to four atomic percent. It is found that our simulation results are in a reasonably good agreement with the experimental measurements of lattice parameter of Al-Zr solid solution obtained by ultra-severe plastic deformation.