c-Myc plays a decisive role in the proliferation of HL-60 promyelocytic leukemia cells. In the present study, we demonstrated that an inhibitor of c-Myc/Max/DNA complex formation has a high potentiality as a suppressor of c-Myc-involved cell signaling. We prepared recombinant c-Myc and Max proteins encompassing the human-origin DNA binding and dimerization domains, and tested a chemical library of 6480 small molecules for their inhibitory effect on the in vitro formation of the c-Myc/Max/DNA complex as well as their influence on DMSO-differentiated HL-60 cells. We found several hit compounds through in vitro and cell-based screening tests, and also confirmed these compounds significantly inhibited the formation of the recombinant c-Myc/Max/DNA complex in the low micromolar range. Indeed, these inhibitors effectively blocked c-Myc-associated gene expression in cancer cell line, suppressed the proliferation and induced the apoptosis of HL-60 promyelocytic leukemia cells via cell cycle arrest without altering the expression level of c-Myc in the DMSO-differentiated HL-60 cells. These successive results suggest that our c-Myc/Max/DNA complex inhibitors potently contribute to the suppression of the Myc-dependent proliferation of leukemia cells and to the induction of apoptosis. Accordingly, we would expect that these compounds could serve as lead compounds in the development of novel anticancer drugs.