Helmholtz free energies of the dominant binary crystalline solids found in the Cu-Zr system at high temperatures close to the melting curve are calculated. Our theoretical approach combines fundamental measure density functional theory (applied to the hard-sphere reference system) and a perturbative approach to include the attractive interactions. The studied crystalline solids are Cu(fcc),Cu51Zr14(β), CuZr(B2), CuZr2(C11b), Zr(hcp), and Zr(bcc). The calculated Helmholtz free energies of crystalline solids are in good agreement with results from molecular-dynamics (MD) simulations. Using the same perturbation approach, the liquid phase free energies are calculated as a function of composition and temperature, from which the melting curve of the entire composition range of this system can be obtained. Phase diagrams are determined in this way for two leading embedded atom method potentials, and the results are compared with experimental data. Theoretical melting temperatures are compared both with experimental values and with values obtained directly from MD simulations at several compositions.