The tumor microenvironment (TME) is the primary arena where tumor cells and the host immune system interact. Bidirectional communication between tumor cells and the associated stromal cell types within the TME influences disease initiation and progression, as well as tumor immunity. Macrophages and natural killer (NK) cells are crucial components of the stromal compartment and display either pro- or anti-tumor properties, depending on the expression of key regulators. MicroRNAs (miRNAs) are emerging as such regulators. They affect several immune cell functions closely related to tumor evasion of the immune system. This review discusses the role of miRNAs in the differentiation, maturation, and activation of immune cells as well as tumor immunity, focusing particularly on macrophages and NK cells.