Hsp70 molecular chaperones function in protein folding in a manner dependent on regulation by co-chaperones. Hsp40s increase the low intrinsic ATPase activity of Hsp70, and nucleotide exchange factors (NEFs) remove ADP after ATP hydrolysis, enabling a new Hsp70 interaction cycle with non-native protein substrate. Here, we show that members of the Hsp70-related Hsp110 family cooperate with Hsp70 in protein folding in the eukaryotic cytosol. Mammalian Hsp110 and the yeast homologues Sse1p/2p catalyze efficient nucleotide exchange on Hsp70 and its orthologue in Saccharomyces cerevisiae, Ssa1p, respectively. Moreover, Sse1p has the same effect on Ssb1p, a ribosome-associated isoform of Hsp70 in yeast. Mutational analysis revealed that the N-terminal ATPase domain and the ultimate C-terminus of Sse1p are required for nucleotide exchange activity. The Hsp110 homologues significantly increase the rate and yield of Hsp70-mediated re-folding of thermally denatured firefly luciferase in vitro. Similarly, deletion of SSE1 causes a firefly luciferase folding defect in yeast cells under heat stress in vivo. Our data indicate that Hsp110 proteins are important components of the eukaryotic Hsp70 machinery of protein folding.