The Cloud-Edge continuum has become a central paradigm for delivering digital services, combining the scalability of centralized Cloud infrastructures with the low-latency benefits of distributed Edge resources. However, orchestrating services across this continuum is increasingly complex, as it must balance multiple and often conflicting objectives. Among these, sustainability considerations, such as the integration of renewable energy sources, are gaining importance, yet they introduce new challenges traditionally absent from energy minimization approaches. Indeed, the growing integration of renewable energy sources brings variability and uncertainty that must be managed alongside service-level requirements such as stability and robustness. This variability complicates orchestration decisions, especially in dynamic and heterogeneous environments where both voluntary and involuntary node departures may occur. Orchestration represents both a challenge and a lever for the energy management of future systems of this type that will be deployed on a global scale. Faced with current environmental concerns and the growing and plethora of heterogeneous and scattered resources involved in these systems, it is imperative to rethink the design of orchestration methods from the additional perspective of sustainability and efficiency. In this thesis, we present an in-depth investigation of service orchestration in renewable energy-enabled Edge computing environments. First, we introduce a comprehensive classification framework specifically designed for sustainable Edge service orchestration across traditional and renewable energy contexts. This review strengthens the critical importance of addressing sustainability concerns and demonstrates how virtualization and service orchestration constitute fundamental foundations for future energy-efficient, distributed ICT infrastructures. Then, we propose a system model that captures the interactions among renewable energy generation, Edge infrastructures, and service robustness. Building on this model, we design an algorithm for service placement and placement reconfiguration, using predictions of energy availability and workload demand to enable more efficient and sustainable orchestration decisions. Finally, we introduce an architecture that instantiates the proposed theoretical models into a practical, standards-compliant solution. Collectively, these contributions provide novel and effective approaches to the challenge of service orchestration in renewable energy-enabled Edge computing settings.