Electric vehicles (EVs) are now widely acknowledged as ideal means of transportation in future, in terms of energy conservation and environmental protection for urban governance. EV lease service is an effective measure to promote the use of EVs and has gained the support of many countries. In this article, a comprehensive pricing scheme is developed to optimize the annual operations profit for EV lease service based on mileage-based pricing (MBP), where the profit is defined as the revenue subtracted by the maintenance cost. Different from the traditional MBP for vehicle lease service, our model characterizes how the grade level of EVs affects the maintenance cost after each failure. Moreover, the lease service is modeled as a queuing system where each consumer has the probability choosing the MBP by comparing the service value and his expense. An enumerative algorithm is developed to find the optimal pricing as well as analyze the influence of parameters on the optimal profit. The algorithm is implemented in the pricing of an EV lease company in China. The results show that the optimal pricing will increase with service rate, consumer arrival rate, and the service value from lessor, but decrease with waiting cost of consumers. Differential pricing strategies are also proposed to resolve the conflict goals of lessors and consumers, which can further boost lessors’ profit and raise consumers’ satisfaction level. The results show that MBP with differential pricing strategies will increase profit between 2.3% and 69.8%, comparing with cases without differential pricing strategies.