Middleboxes are widely deployed to perform various network functions to ensure security and improve performance. The recent trend of Network Function Virtualization (NFV) makes it easy for operators to deploy software implementations of these network functions on commodity servers. However, virtual network functions consume different amounts of resources when processing packets. Thus a multi-resource load balancing (MRLB) mechanism is needed to efficiently utilize server resources. MRLB problem in the context of NFV is fundamentally different from multi-resource allocation problems, as well as traditional single-resource load balancing and multi-resource load balancing problems in task scheduling. In this paper, we tackle the MRLB problem in NFV by first proposing dominant load—the load of the most stressed resource on a server—as the load balancing metric. We then formulate the MRLB problem as an optimization to minimize the maximum dominant load of all NFV servers given the demand. Based on proximal Jacobian ADMM, we propose an efficient algorithm to solve the problem in large scale settings. Through extensive trace-driven simulations and prototype experiments on a testbed, we show that our MRLB algorithm with dominant load performs significantly better and faster than benchmarking algorithms.