A future heavy-ion program at J-PARC has been discussed. The QCD phase structure in high baryon density regime will be explored with heavy ions at the beam momenta of around 10 A GeV/c at the beam rate of 1010–1011 Hz. For this quest, a large acceptance spectrometer is designed to measure electrons and muons, and rare probes such as multi-strangeness and charmed hadrons/nuclei. A heavy-ion acceleration scheme is under study with a new heavy-ion linac and a new booster ring, which accelerate and inject beams into the existing Rapid-Cycling Synchrotron and Main Ring synchrotron. An overview of the heavy-ion program and an accelerator design, as well as physics goals and a conceptual design of the heavy-ion experiment are discussed.