Even and equitable distribution of the COVID-19 vaccine becomes one of key strategies to reduce the number of positive cases and virus transmissions all over the world. This paper aims to introduce and demonstrate a mathematical model based on a maximal covering location problem (MCLP) to optimise the coverage of the COVID-19 vaccine distribution. A mathematical model is proposed and demonstrated using an illustrative case study of healthcare facilities and location coordinates of villages in Yogyakarta, Indonesia. A numerical computer experiment is conducted to obtain optimal results of the locational analysis. The results show that the proposed model provides an efficient coverage of vaccination by minimising the distances travelled by the target population. It also reveals an interesting insight that prioritising vaccination for areas with high COVID-19 cases results in a less efficient coverage. The novel location-allocation model for COVID-19 vaccination facilities proposed in this paper particularly applies in a developing country. The model could be used as an alternative way to increase the vaccination coverage and priority whilst minimising the potential risks of the virus transmissions and transport costs.