We show by molecular dynamics simulations that the melting temperature of clusters can be tuned by selective doping. In fact, a single Ni or Cu impurity in Ag icosahedral clusters considerably increases the melting temperature even for sizes of more than a hundred atoms. The upward shift is correlated to the strain relaxation induced by a small central impurity in icosahedral clusters.