It is widely believed that, in contrast to its electron doped counterparts, the hole doped compound Ba1-xKxFe2As2 exhibits a mesoscopic phase separation of magnetism and superconductivity in the underdoped region of the phase diagram. Here, we report a combined high-resolution x-ray powder diffraction and volume sensitive muon spin rotation study of underdoped Ba1-xKxFe2As2 (0 leq x leq 0.25) showing that this paradigm is wrong. Instead we find a microscopic coexistence of the two forms of order. A competition of magnetism and superconductivity is evident from a significant reduction of the magnetic moment and a concomitant decrease of the magneto-elastically coupled orthorhombic lattice distortion below the superconducting phase transition.