Sustainable energy supply is an essential part for economic and social development in every society. Islands as geographical isolated regions have to confront a number of challenges to secure a reliable and clean energy system. Currently, electricity demand on the Greek island of Crete is supplied by oil-fired engines imposed to new emissions restrictions applied from 2020. Thus, a capacity upgrade is necessary and new solutions driven by renewable energy, energy storage and interconnections. This study investigates three scenarios: Business as Usual (BAU); Natural Gas (NG); and the Interconnection of Crete with the National Grid System (Int.) to assess the potential techno-economic and environmental impact of the required transition under the Energy Trilemma Index. A capacity expansion and operation optimisation process has been applied through a high resolution spatio-temporal analysis performed with PLEXOS Integrated Energy Model. It was concluded that no BAU Scenario could facilitate a future plan for the electricity system of Crete or any European island imposed to such constrains. The optimum scenario incorporates interconnectors and energy storage systems that manage to deliver 52% reduction in the total system costs (2020-2040), 79% in electricity prices and 48% reduction in GHG emissions by 2040, compared to the BAU.