Vaccines are crucial to curb infectious-disease epidemics. Indeed, one of the highest priorities of the National Institutes of Health (NIH) on the HIV front is the development and delivery of a vaccine that is at least moderately effective. However, risk compensation could undermine the ability of partially-effective vaccines to curb epidemics: Since vaccines reduce the cost of risky interactions, vaccinated agents may optimally choose to engage in more of them and, as a result, may increase everyone’s infection probability. We show that—in contrast to the prediction of standard models—things can be worse than that: A free and perfectly safe but only partially effective vaccine can reduce everyone’s welfare. The reason is simple: By reducing the cost of risky interactions, a partially-effective vaccine can destabilize the existing interaction structure in favor of a less efficient one. Because of the strategic complementarities in risky interactions that we show a rise when agents strategically choose their partners, the most efficient stable interaction structure after the introduction of a partially-effective vaccine can be much denser and—due to the negative externalities of risky interactions—worse for everyone. The result of this paper underscorestheimportanceoftakingintoaccounttheeffectsthatdifferentinterventions have on social structure, and it suggests that the NIH might want to go big—i.e. deliver a highly-effective vaccine—or go home.