The distribution of valence electrons in metals usually follows the symmetry of an ionic lattice. Modulations of this distribution often occur when those electrons are not stable with respect to a new electronic order, such as spin or charge density waves. Electron density waves have been observed in many families of superconductors[1-3], and are often considered to be essential for superconductivity to exist[4]. Recent measurements[5-9] seem to show that the properties of the iron pnictides[10, 11] are in good agreement with band structure calculations that do not include additional ordering, implying no relation between density waves and superconductivity in those materials[12-15]. Here we report that the electronic structure of Ba1-xKxFe2As2 is in sharp disagreement with those band structure calculations[12-15], instead revealing a reconstruction characterized by a (pi,pi) wave vector. This electronic order coexists with superconductivity and persists up to room temperature.