Precursor states of Multiple Myeloma (MM) and its native tumor microenvironment need in-depth molecular characterization to better stratify and treat patients at risk. Using single-cell RNA sequencing of bone marrow cells from precursor stages, MGUS and smoldering myeloma (SMM), to full-blown MM alongside healthy donors, we demonstrate early immune changes during patient progression. We find NK cell abundance is frequently increased in early stages, and associated with altered chemokine receptor expression. As early as SMM, we show loss of GrK(+) memory cytotoxic T-cells, and show their critical role in MM immunosurveillance in mouse models. Finally, we report MHC class II dysregulation in CD14(+) monocytes, which results in T cell suppression in vitro. These results provide a comprehensive map of immune changes at play over the evolution of pre-malignant MM, which will help develop strategies for immune-based patient stratification.