Immune checkpoint inhibition (ICI) has revolutionized cancer therapy. However, response to ICI is often limited to selected subsets of patients or not durable. Tumors that are non-responsive to checkpoint inhibition are characterized by low anti-tumoral immune cell infiltration and a highly immunosuppressive tumor microenvironment. Exercise is known to promote immune cell circulation and improve immunosurveillance. Results of recent studies indicate that physical activity can induce mobilization and redistribution of immune cells towards the tumor microenvironment (TME) and therefore enhance anti-tumor immunity. This suggests a favorable impact of exercise on the efficacy of ICI. Our review delivers insight into possible molecular mechanisms of the crosstalk between muscle, tumor, and immune cells. It summarizes current data on exercise-induced effects on anti-tumor immunity and ICI in mice and men. We consider preclinical and clinical study design challenges and discuss the role of cancer type, exercise frequency, intensity, time, and type (FITT) and immune sensitivity as critical factors for exercise-induced impact on cancer immunosurveillance.