Inhibition of immune regulatory checkpoints, such as CTLA-4 and the PD-1-PD-L1 axis, is at the forefront of immunotherapy for cancers of various histological types. However, such immunotherapies fail to control neoplasia in a significant proportion of patients. Here, we review how a range of cancer-cell-autonomous cues, tumor-microenvironmental factors, and host-related influences might account for the heterogeneous responses and failures often encountered during therapies using immune-checkpoint blockade. Furthermore, we describe the emerging evidence of how the strong interrelationship between the immune system and the host microbiota can determine responses to cancer therapies, and we introduce a concept by which prior or concomitant modulation of the gut microbiome could optimize therapeutic outcomes upon immune-checkpoint blockade.