We consider the amount of work which can be extracted from a heat bath using a bipartite state rho shared by two parties. In general it is less then the amount of work extractable when one party is in possession of the entire state. We derive bounds for this "work deficit" and calculate it explicitly for a number of different cases. In particuar, for pure states the work deficit is exactly equal to the distillable entanglement of the state. A form of complementarity exists between physical work which can be extracted and distillable entanglement. The work deficit is a good measure of the quantum correlations in a state and provides a new paradigm for understanding quantum nonlocality.