Melchior ble født i en rabbinerfamilie i København, og fikk sin semikhá (ordinasjon) som rabbiner fra Yeshivat Hakotel i Jerusalem. Han arbeidet i mange år som rabbiner i Det Mosaiske Trossamfund i Oslo.
Siden 1985 har Melchior og hans familie hovedsakelig bodd i Israel. Hans sønn Joav ble senere rabbiner i Oslo. Han ble leder for Meimad i 1996 og i 1999, året da Meimad ble et parti, ble han innvalgt i Knesset. Han er partiets eneste representant.
Etter at Barak tapte valget i 2001, ble han i stedet utnevnt til viseutenriksminister for diaspora-anliggender under Shimon Peres, men mistet denne stillingen da Arbeiderpartiet trakk seg fra regjeringen i november 2002. Han ble gjenvalgt til Knesset i 2003.
I januar 2005 ble han utnevnt til viseminister for utdannelse, kultur og sport, etter at Arbeiderpartiet hadde gått inn i regjeringen igjen. I juni 2006 ble han viseminister for sosiale- og diasporasaker, men gikk igjen av etter at Arbeiderpartiet trakk seg ut av regjeringen.
Melchior ble gjenvalgt som Knessetmedlem i 2006, og ble da leder for komiteen for utdannelse, kultur og sport.
