Rab GTPases are key regulators of membrane traffic pathways within eukaryotic cells. They are specifically activated by guanine nucleotide exchange factors (GEFs), which convert them from their "inactive" GDP-bound form to the "active" GTP-bound form. In higher eukaryotes, proteins containing DENN-domains comprise a major GEF family. Here we describe at 2.1-Å resolution the first structure of a DENN-domain protein, DENND1B-S, complexed with its substrate Rab35, providing novel insights as to how DENN-domain GEFs interact with and activate Rabs. DENND1B-S is bi-lobed, and interactions with Rab35 are through conserved surfaces in both lobes. Rab35 binds via switch regions I and II, around the nucleotide-binding pocket. Positional shifts in Rab residues required for nucleotide binding may lower its affinity for bound GDP, and a conformational change in switch I, which makes the nucleotide-binding pocket more solvent accessible, likely also facilitates exchange.