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 but only partially effective vaccine can make 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 arise 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 underscores the importance of taking into account the effects that different interventions 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.