We consider the capacitated facility location problem (CFLP) with differentiable convex production cost functions. The problem arises in numerous real-world applications as queues in call-centres, serverqueueing or when production is pushed beyond normal capacity limits. For finding proven optimal solutions, we suggest a branch-and-bound algorithm based on Lagrangian relaxation and subgradient optimization. The algorithm basically extends a similar method for the classical linear cost CFLP to the convex cost case. The method is compared on a large number of test instances to three other exact solution approaches: The use of perspective cuts, a second-order cone (SOC) MIP formulation for the case of quadratic costs, and Benders’ decomposition. Our computational results indicate that in many case the branch-and-bound method is superior to both the perspective cut approach, the SOC MIP, and the application of Benders’ decomposition.