We study the melting behavior of charged colloidal crystals, using a simulation technique that combines a continuous mean-field Poisson-Boltzmann description for the microscopic electrolyte ions with a Brownian-dynamics simulation for the mesoscopic colloids. This technique ensures that many-body interactions among the colloids are fully taken into account, and thus allows us to investigate how many-body interactions affect the solid-liquid phase behavior of charged colloids. Using the Lindemann criterion, we determine the melting line in a phase-diagram spanned by the colloidal charge and the salt concentration. We compare our results to predictions based on the established description of colloidal suspensions in terms of pairwise additive Yukawa potentials, and find good agreement at high-salt, but not at low-salt concentration. Analyzing the effective pair-interaction between two colloids in a crystalline environment, we demonstrate that the difference in the melting behavior observed at low salt is due to many-body interactions. If the salt concentration is high, we find configuration-independent pair forces of perfect Yukawa form with effective charges and screening constants that are in good agreement with well-established theories. At low added salt, however, the pair forces are Yukawa-type only at short distances with effective parameters that depend on the analyzed colloidal configuration. At larger distances, the pair-forces decay to zero much faster than they would following a Yukawa force law. Based on these findings, we suggest a simple model potential for colloids in suspension which has the form of a Yukawa potential, truncated after the first coordination shell of a colloid in a crystal. Using this potential in a one-component simulation, we find a melting line that shows good agreement with the one derived from the full Poisson-Boltzmann-Brownian-dynamics simulation. (C) 2003 American Institute of Physics.