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, monoclonal gammopathy of unknown significance and smoldering MM, to full-blown MM alongside healthy donors, we demonstrate early immune changes during patient progression. We find that natural killer cell abundance is frequently increased in the early stages and associated with altered chemokine receptor expression. As early as smoldering MM, we show loss of granzyme K⁺ memory cytotoxic T cells and show their critical role in MM immunosurveillance in mouse models. Finally, we report major histocompatibility complex 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 premalignant MM, which will help develop strategies for immune-based patient stratification.