Objective: Vaccine hesitancy has been ranked by the World Health Organization among the top 10 threats to global health. With a surge in misinformation and conspiracy theories against vaccination observed during the COVID-19 pandemic, attitudes toward vaccination may be worsening. This study investigates trends in anti-vaccination attitudes during the COVID-19 pandemic and within the United States, Canada, the United Kingdom, and Australia. Methods: Vaccine-related English tweets published between 1 January 2020 and 27 June 2021 were used. A deep learning model using a dynamic word embedding method, Bidirectional Encoder Representations from Transformers (BERTs), was developed to identify anti-vaccination tweets. The classifier achieved a micro F1 score of 0.92. Time series plots and country maps were used to examine vaccination attitudes globally and within countries. Results: Among 9,352,509 tweets, 232,975 (2.49%) were identified as anti-vaccination tweets. The overall number of vaccine-related tweets increased sharply after the implementation of the first vaccination round since November 2020 (daily average of 6967 before vs. 31,757 tweets after 9/11/2020). The number of anti-vaccination tweets increased after conspiracy theories spread on social media. Percentages of anti-vaccination tweets were 3.45%, 2.74%, 2.46%, and 1.86% for the United States, the United Kingdom, Australia, and Canada, respectively. Conclusions: Strategies and information campaigns targeting vaccination misinformation may need to be specifically designed for regions with the highest anti-vaccination Twitter activity and when new vaccination campaigns are initiated.