The increasing penetration of electrical vehicles (EVs), on the way to decarbonizing the transportation sector, presents several challenges and opportunities for the end users, the distribution grid, and the electricity markets. Uncontrollable EV charging may increase peak demand and impact the grid stability and reliability, especially in the case of non-interconnected microgrids such as the distribution grids of small islands. On the other hand, if EVs are considered as flexible loads and distributed storage, they may offer Vehicle to Grid (V2G) services and contribute to demand-side management through smart charging and discharging. In this work, we present a study on the penetration of EVs and the flexibility they may offer for services to the grid, using a genetic algorithm for optimum valley filling and peak shaving for the case of a non-interconnected island where the electricity demand is several times higher during the summer due to the influx of tourists. Test cases have been developed for various charging/discharging strategies and mobility patterns. Their results are discussed with respect to the current generating capacity of the island as well as the future case where part of the electricity demand will have to be met by renewable energy sources, such as photovoltaic plants, in order to minimize the island’s carbon footprint. Higher EV penetration, in the range of 20−25%, is enabled through smart charging strategies and V2G services, especially for load profiles with a large difference between the peak and low demands. However, the EV penetration and available flexibility is subject to the mobility needs and limited by the population and the size of the road network of the island itself rather than the grid needs and constraints. Limitations and challenges concerning efficient V2G services on a non-interconnected microgrid are identified. The results will be used in the design of a smart charging controller linked to the microgrid’s energy management system.