Leukemia cells are protected from chemotherapy-induced apoptosis by their interactions with bone marrow mesenchymal stromal cells (BM-MSCs). Yet the underlying mechanisms associated with this protective effect remain unclear. Genome-wide gene expression profiling of BM-MSCs revealed that coculture with leukemia cells upregulated the transcription of genes associated with nuclear factor (NF)-κB signaling. Moreover, primary BM-MSCs from leukemia patients expressed NF-κB target genes at higher levels than their normal BM-MSC counterparts. The blockade of NF-κB activation via chemical agents or the overexpression of the mutant form of inhibitor κB-α (IκBα) in BM-MSCs markedly reduced the stromal-mediated drug resistance in leukemia cells in vitro and in vivo. In particular, our unique in vivo model of human leukemia BM microenvironment illustrated a direct link between NF-κB activation and stromal-associated chemoprotection. Mechanistic in vitro studies revealed that the interaction between vascular cell adhesion molecule 1 (VCAM-1) and very late antigen-4 (VLA-4) played an integral role in the activation of NF-κB in the stromal and tumor cell compartments. Together, these results suggest that reciprocal NF-κB activation in BM-MSCs and leukemia cells is essential for promoting chemoresistance in the transformed cells, and targeting NF-κB or VLA-4/VCAM-1 signaling could be a clinically relevant mechanism to overcome stroma-mediated chemoresistance in BM-resident leukemia cells.