A modified version of the SEIR model with the effects of vaccination and inter-state movement is proposed to simulate the spread of COVID-19 in Malaysia. A mathematical analysis of the proposed model was performed to derive the basic reproduction number. To enhance the model’s forecasting capabilities, the model parameters were estimated using the Nelder–Mead simplex method by fitting the model outputs to the observed data. Our results showed a good fit between the model outputs and available data, where the model was then able to perform short-term predictions. In line with the rapid vaccination program, our model predicted that the COVID-19 cases in the country would decrease by the end of August. Furthermore, our findings indicated that relaxing travel restrictions from a highly vaccinated region to a low vaccinated region would result in an epidemic outbreak.