The decision of whether or not to vaccinate is a complex one. It involves the contribution both to a social good—herd immunity—and to one’s own well-being. It is informed by social influence, personal experience, education, and mass media. In our work, we investigate a situation in which individuals make their choice based on how social neighbourhood responded to previous epidemics. We do this by proposing a minimalistic model using components from game theory, network theory and the modelling of epidemic spreading, and opinion dynamics. Individuals can use the information about the neighbourhood in two ways—either they follow the majority or the best-performing neighbour. Furthermore, we let individuals learn which of these two decision-making strategies to follow from their experience. Our results show that the flexibility of individuals to choose how to integrate information from the neighbourhood increases the vaccine uptake and decreases the epidemic severity if the following conditions are fulfilled. First, the initial fraction of individuals who imitate the neighbourhood majority should be limited, and second, the memory of previous outbreaks should be sufficiently long. These results have implications for the acceptance of novel vaccines and raising awareness about vaccination, while also pointing to promising future research directions.