Rhabdomyosarcomas (RMS) are rare and often lethal diseases. It is assumed that the tumor microenvironment (TME) of RMS exerts an immunosuppressive function, but there is currently no systematic analysis of the immune cells infiltrating sarcoma tissue. Focusing on two common types of RMS (alveolar [RMA] and embryonal [RME]), we performed a comprehensive immunohistochemical analysis of tumor-infiltrating immune cells in the TME. We performed a qualitative estimation of infiltrating immune cells in the tumor microenvironment by an experienced pathologist as well as a quantitative digital pathology analysis. We found that (1) manual and automatic quantification of tumor-infiltrating immune cells were consistent; (2) RME tumors showed a higher degree of immune cell infiltration than RMA tumors but (3) the number of tumor infiltrating lymphocytes was low compared to other solid tumor types; (4) microvascular density correlated with immune cell infiltration and (5) CD163 positive macrophages as well as CD54 positive microvessels were more often detected in RME than in RMA and correlated with patient overall and event free survival. Our systematic analysis provides a comprehensive view of the immune landscape of RMS which needs to be taken into account for developing immunotherapies for this rare type of cancer.