We present the first ab initio construction of valence-space Hamiltonians for medium-mass nuclei based on chiral two- and three-nucleon interactions using the in-medium similarity renormalization group. When applied to the oxygen isotopes, we find experimental ground-state energies are well reproduced, including the flat trend beyond the drip line at (24)O. Similarly, natural-parity spectra in (21,22,23,24)O are in agreement with experiment, and we present predictions for excited states in (25,26)O. The results exhibit a weak dependence on the harmonic-oscillator basis parameter and reproduce spectroscopy within the standard sd valence space.