Current cancer therapeutics often insufficiently eradicate malignant cells due to the surrounding dense tumor stroma. This multi-componential tissue consists of mainly cancer-associated fibroblasts, the (compact) extracellular matrix, tumor vasculature, and tumor-associated macrophages, which all exert crucial roles in maintaining a pro-tumoral niche. Their continuous complex interactions with tumor cells promote tumor progression and metastasis, emphasizing the challenges in tumor therapy development. Over the last decade, advances in oncolytic virotherapy have shown that oncolytic viruses (OVs) are a promising multi-faceted therapeutic platform for simultaneous tumor and stroma targeting. In addition to promoting tumor cell oncolysis and systemic anti-tumor immunity, accumulating data suggest that OVs can also directly target stromal components, facilitating OV replication and spread, as well as promoting anti-tumor activity. This review provides a comprehensive overview of the interactions between native and genetically modified OVs and the different targetable tumor stromal components, and outlines strategies to improve stroma targeting by OVs.