Andean blueberry is a promissory fruit native to South America. The current work aimed to characterize starches isolated from Colombian native potatoes and to evaluate the effect of the application of starch edible coatings on the changes in the physicochemical quality parameters of the Andean blueberry during storage. Starches were isolated from three different potatoes varieties (pacha negra, mora, and alcarrosa) and characterized. Then, starch-based coatings were applied to Andean blueberries, and the changes in their quality parameters were monitored during 12 days of storage. Despite the phenotypical differences in the starch sources used, starches were similar in terms of their granule morphology, amylose content (~19%), crystallinity degree (~46%), and thermal properties. Coatings were able to reduce the gaseous exchange of the fruit, and, thus, the respiration rate of all coated blueberries was ~27% lower compared to the uncoated fruits (p < 0.05) at the end of the storage. While the application of starch coatings did not prevent water loss, all samples reached water loss of up 20%. Besides, the coated fruits showed soluble solids contents ~14% higher compared to the control one, as well as better bright and firmness. The new edible coatings can help add value to the Andean blueberry.