Public perception about vaccines is imperative for successful vaccination programs. This study aims to measure the shift of sentiment towards vaccines after the COVID-19 outbreak in the Arab-speaking population. The study used vaccine-related Arabic Tweets and analyzed the sentiment of users in two different time frames, before 2020 (T1) and after 2020 (T2). The analysis showed that in T1, 48.05% of tweets were positive, and 16.47% of tweets were negative. In T2, 43.03% of tweets were positive, and 20.56% of tweets were negative. Among the Twitter users, the sentiment of 15.92% users shifted towards positive, and the sentiment of 17.90% users shifted towards negative. Public sentiment that have shifted towards positive may be due to the hope of vaccine efficacy, whereas public sentiment that have shifted towards negative may be due to the concerns related to vaccine side effects and misinformation. This study can support policymakers in the Arab world to combat the COVID-19 pandemic by utilizing tools to understand public opinion and sentiment.