A growing tendency to refuse child vaccination is commonly regarded as a reason for concern. Attempts to promote vaccination by authorities often prove to be unsuccessful or even counter-productive. The aim of this study was to explore how parents perceived four messages used to promote vaccination. In eight focus groups (N = 73), we presented participants with messages and asked them to assess them. Using thematic analysis, we identified themes that our participants considered the most important. Messages that promote vaccination should be unambiguous, more balanced, not focus on repeating the negative effects of vaccine-preventable diseases and provide links to the evidence.