We present the detection, performed with the Westerbork Synthesis Radio Telescope (WSRT) and the Karl Jansky Very Large Array (VLA), of a fast HI 21-cm outflow in the ultra-luminous infrared galaxy Mrk 231. The outflow is observed as shallow HI absorption blueshifted ~1300 km/s with respect to the systemic velocity and located against the inner kpc of the radio source. The outflowing gas has an estimated column density between 5 and 15x10^18 Tspin cm^-2. We derive the Tspin to lie in the range 400-2000 K and the densities are n_HI~10-100 cm^-3. Our results confirm the multiphase nature of the outflow in Mrk231. Although effects of the interaction between the radio plasma and the surrounding medium cannot be ruled out, the energetics and the lack of a clear kpc-scale jet suggest that the most likely origin of the HI outflow is a wide-angle nuclear wind, as earlier proposed to explain the neutral outflow traced by NaI and molecular gas. Our results suggest that an HI component is present in fast outflows regardless of the acceleration mechanism (wind vs jet driven) and that it must be connected with common properties of the pre-interaction gas. Considering the observed similarity of their column densities, the HI outflow likely represents the inner part of the broad wind identified on larger scales in NaI. The mass outflow rate of the HI outflow does not appear to be as large as the one observed in molecular gas. These characteristics suggest that the HI may represent a short intermediate phase in the rapid cooling of the gas. We also obtained deeper continuum images than previously available. At the resolution of ~1arcsec we do not see a kpc-scale jet. Instead, we detect a plateau of emission, likely due to star formation, surrounding the bright nuclear region. We also detect a poorly collimated bridge which may represent the channel feeding the southern lobe.