We consider using a battery storage system simultaneously for peak shaving and frequency regulation through a joint optimization framework which captures battery degradation, operational constraints and uncertainties in customer load and regulation signals. Under this framework, using real data we show the electricity bill of users can be reduced by up to 15\%. Furthermore, we demonstrate that the saving from joint optimization is often larger than the sum of the optimal savings when the battery is used for the two individual applications. A simple threshold real-time algorithm is proposed and achieves this super-linear gain. Compared to prior works that focused on using battery storage systems for single applications, our results suggest that batteries can achieve much larger economic benefits than previously thought if they jointly provide multiple services.