The optimal design of hybrid power generation systems (HPGS) can significantly improve the economic and technical performance of power supply. Due to the intermittent nature of renewable energy sources, as well as the application of energy storage techniques, the efficacy and efficiency of reliability assessment have become vital for successful HPGS design optimization. This paper proposes a sizing optimization method for HPGS based on a Markovian approach for long term reliability assessment. A multi-scenario formulation is considered to minimize the system cost while guaranteeing acceptable reliability across all the representative scenarios. The presented reliability analysis approach employs a Markov chain to model the state of charge of the energy storage based on probabilistic resource and load models. With this treatment, the loss of load probability of the HPGS can be tracked with relatively low computation, making it suitable for optimization applications. The effectiveness of the reliability analysis approach is tested through a comparison with Monte Carlo simulation; then the optimization approach is demonstrated with a numerical case study.