Accumulating evidence indicates that myeloid cells are critically involved in the pathophysiology of human cancers. In contrast to the well-characterized tumor-associated macrophages, the significance of granulocytes in cancer has only recently begun to emerge. A number of studies found increased numbers of neutrophil granulocytes and granulocytic myeloid-derived suppressor cells (GrMDSCs) both in the peripheral blood and in the tumor tissues of patients with different types of cancer. Most importantly, granulocytes have been linked to poor clinical outcome in cancer patients which suggests that these cells might have important tumor-promoting effects. In this review, we will address in detail the following major topics: (1) neutrophils and GrMDSCs in the peripheral blood of cancer patients—phenotype and functional changes; (2) neutrophils and GrMDSCs in the tumor tissue—potential mechanisms of tumor progression and (3) relevance of neutrophils and GrMDSCs for the clinical outcome of cancer patients. Furthermore, we will discuss the advantages and disadvantages of the current strategies used for identification and monitoring of human MDSCs. We propose a six-color immunophenotyping protocol that discriminates between monocytic MDSCs (MoMDSCs), two subsets of GrMDSCs and two subsets of immature myeloid cells in human cancer patients, thus, allowing for an improved characterization and understanding of these multifaceted cells.