We consider the electric vehicle (EVs) charging problem with heterogeneous maximum charging rates and time-varying power capacity. Focusing on the feasibility problem that aims to satisfy all EVs’ energy demands prior to their departure, we propose an online algorithm, smoothed least-laxity-€rst (sLLF) to schedule EV charging and characterize its performance using the resource augmentation framework. We derive the minimum amount of augmentation to power capacity and to EVs’ maximum charging rates for sLLF to be online feasible. Numerical experiments on real EV charging data show that sLLF performs significantly better than several common online algorithms.