Immune checkpoint inhibitors (ICI) used for cancer immunotherapy were shown to boost the existing anti-tumor immune response by preventing the inhibition of T cells by tumor cells. Antibodies targeting two negative immune checkpoint pathways, namely cytotoxic T-lymphocyte-associated protein 4 (CTLA-4), programmed cell death protein 1 (PD-1), and programmed cell death-ligand 1 (PD-L1), have been approved first for patients with melanoma, squamous non-small cell lung cancer (NSCLC), and renal cell carcinoma. Clinical trials are ongoing to verify the efficiency of these antibodies for other cancer types and to evaluate strategies to block other checkpoint molecules. However, a number of patients do not respond to this treatment possibly due to profound immunosuppression, which is mediated partly by myeloid-derived suppressor cells (MDSC). This heterogeneous population of immature myeloid cells can strongly inhibit anti-tumor activities of T and NK cells and stimulate regulatory T cells (Treg), leading to tumor progression. Moreover, MDSC can contribute to patient resistance to immune checkpoint inhibition. Accumulating evidence demonstrates that the frequency and immunosuppressive function of MDSC in cancer patients can be used as a predictive marker for therapy response. This review focuses on the role of MDSC in immune checkpoint inhibition and provides an analysis of combination strategies for MDSC targeting together with ICI to improve their therapeutic efficiency in cancer patients.