We present systematic first-principles calculations for impurity-impurity interaction energies (Eint) of 4d elements in 4d bcc metals Nb and Mo, and 4d fcc metals Pd and Ag. The calculations are based on the generalized-gradient approximation in density-functional formalism, proposed by Perdew and Wang in 1991 (PW91-GGA), and apply the full-potential Korringa-Kohn-Rostoker (FPKKR) Green’s function method for point defects, developed by the Jülich group. First we examine the distance dependence, from 1st to 8th neighbors, of Eint and show that for most cases, the 1st nearest-neighboring impurity-impurity interaction energies (Eint1) are dominant. Second it is shown that most of the types of phase diagrams of binary alloys of impurity and host elements, such as segregation, solid solution, and order, known experimentally, may be very well discriminated by use of the sign and magnitude of Eint1. Third we show that the temperature dependence of solid solubility limit of Rh in Pd, which is segregated at low temperatures and becomes disordered at high temperatures, are reproduced fairly well by the free-energy calculations based on the cluster variation method with the present results for Eint (up to the 8th neighbor). It is also shown that the inclusion of the impurity-cluster interaction energies up to the four-body (a tetrahedron of 1st-nearest neighbors), being also determined by the present first principles calculations, leads to the complete agreement with the experimental result. We also show that the chemical trend for Eint1 is understood by use of the Friedel’s band filling mechanism for d-states, if the dependence of the band width on element is taken into account in the model.