The COVID-19 vaccine will be distributed throughout the country by the government, one of which is Indonesia. COVID-19 vaccine is a perishable good. Therefore, cold chain planning is necessary for the COVID-19 vaccine distribution. This research aims to determine the priority order of Indonesia's provinces to receive vaccines and vaccine distribution alternatives. This study uses Microsoft Office Excel 2013 with the help of a solver tool for processing the Vehicle Routing Problems (VRP). The result shows that the top 7 provinces that need to be prioritized based on the frequency distribution categorization result until September 30, 2020, for vaccine distribution are DKI Jakarta, East Java, Central Java, West Java, South Sulawesi, South Kalimantan, and North Sumatra. The results of the alternative planning show that the longest total distance from alternative 1 in DKI Jakarta is 121 km for 26.03 hours, alternative 2 in DKI Jakarta is 58 km for 11.9 hours, alternative 1 in Papua is 608 km for 35.78 hours, alternative 2 in Papua is 315 km for 12.5 hours.