As a crucial arm of innate immunity, the complement cascade (ComC) is involved both in mobilization of normal hematopoietic stem/progenitor cells (HSPCs) from bone marrow (BM) into peripheral blood (PB) and in their homing to BM. Despite the fact that ComC cleavage fragments alone do not chemoattract normal HSPCs, we found that leukemia cell lines as well as clonogenic blasts from CML and AML patients respond robustly to C3 and C5 cleavage fragments by chemotaxis and increased adhesion. This finding was supported by the detection of C3a and C5a receptors in cells from human malignant hematopoietic cell lines and patient blasts at the mRNA (RT-PCR) and protein level (FACS) and by the demonstration that these receptors respond to stimulation by C3a and C5a by phosphorylation of p42/44 and p38 MAPK and AKT. We also found that inducible heme oxygenase 1 (HO-1) is a negative regulator of ComC-mediated trafficking of leukemic cells and that stimulation of leukemic cells by C3 or C5 cleavage fragments activates p38 MAPK, which downregulates HO-1 expression, rendering cells more mobile. We conclude that activation of the ComC in leukemia/lymphoma patients (e.g., as a result of accompanying infections) enhances the motility of malignant cells and contributes to their spread in a p38 MAPK–HO-1-dependent manner. Therefore, inhibition of p38 MAPK or upregulation of HO-1 by small-molecule modulators would have a beneficial effect on ameliorating expansion of leukemia/lymphoma cells when the ComC becomes activated.