The recently discovered Fe-arsenides appear to provide a new paradigm for high temperature superconductivity. Born out of a multiband itinerant antiferromagnetic state, evidence points to spin fluctuations associated with a partially nested Fermi surface playing a decisive role. Significantly, the antiferromagnetic transition in the parent Fe arsenides is always preceded by or coincident with a tetragonal to orthorhombic structural distortion. Since both the long range magnetic order and the superconductivity are born out of this orthorhombic state, understanding its origins is central to developing a comprehensive theory of these materials. Here we show compelling evidence that the orthorhombicity in the representative material Co-doped BaFe2As2 is driven by an electron nematic phase transition, with implications for the pairing interaction. Additional measurements of quantum oscillations in P-doped BaFe2As2 reveal dramatic changes in the Fermi surface topology across the phase diagram, underlining the role played by Fermi surface nesting.