Heparanase is a heparan sulfate-degrading endoglycosidase expressed by mature monocytes and myeloid cells, but not by immature hematopoietic progenitors. Heparanase gene expression is upregulated during differentiation of immature myeloid cells. PML-RARalpha and PLZF-RARalpha fusion gene products associated with acute promyelocytic leukemia abrogate myeloid differentiation and heparanase expression. AML-Eto, a translocation product associated with AML FAB M2, also downregulates heparanase gene expression. The common mechanism that underlines the activity of these three fusion gene products involves the recruitment of histone deacetylase complexes to specific locations within the DNA. We found that retinoic acid that dissociates PML-RARalpha from the DNA, and which is used to treat acute promyelocytic leukemia patients, restores heparanase expression to normal levels in an acute promyelocytic leukemia cell line. The retinoic acid effects were also observed in primary acute promyelocytic leukemia cells and in a retinoic acid-treated acute promyelocytic leukemia patient. Histone deacetylase inhibitor reverses the downregulation of heparanase expression induced by the AML-Eto fusion gene product in M2 type AML. In summary, we have characterized a link between leukomogenic factors and the downregulation of heparanase in myeloid leukemic cells.