The Energy Storage System (ESS) is an expensive component of an E-bike. The idea of Hybrid Energy Storage System (HESS), a combination between battery and Ultra-Capacitor (UC), can moderate the cost of E-bike ESS. In this paper, a cost function is developed to use for optimal sizing of a HESS. This cost function is consisted of the HESS (battery, UC and DC/DC converter) cost and the cost of battery replacements during 10 years. The battery lifetime and riding pattern limit the life span of ESS. The “Portuguese standard NP EN 1986-1” riding pattern is used in this research. The Genetic Algorithm (GA) is used to solve the optimization problem. The results show that the cost and weight of HESS are clearly better than optimally sized battery ESS.