We present the first radial velocity measurement of the stellar component of the Local Group dwarf galaxy Phoenix, using the FORS1 instrument at the VLT's Unit Telescope 1 (Antu). From the spectra of 31 red giant branch stars, we derive a heliocentric optical radial velocity for Phoenix of Vsolar=-52+/-6 km s-1. On the basis of this velocity, and taking into account the results of a series of semianalytical and numerical simulations, we discuss the possible association of the H I clouds observed in the Phoenix vicinity. We conclude that the characteristics of the H I cloud with heliocentric velocity -23 km s-1 are consistent with this gas having been associated with Phoenix in the past and being lost by the galaxy after the last event of star formation in the galaxy, about 100 Myr ago. Two possible scenarios are discussed: the ejection of the gas by the energy released by the supernovae (SNe) produced in that last event of star formation and a ram pressure stripping scenario. We derive that the kinetic energy necessary to eject the gas is ESNe~2×1051 ergs and that the number of SNe necessary to transfer this amount of kinetic energy to the gas cloud is ~20. This is consistent with the number of SNe expected for the last event of star formation in Phoenix, according to the star formation history derived by Martínez-Delgado, Gallart, & Aparicio. The drawback of this scenario is the regular appearance of the H I cloud and its anisotropic distribution with respect to the stellar component. Another possibility is that the H I gas was stripped as a consequence of ram pressure by the intergalactic medium. In our simulations, the structure of the gas remains quite smooth as it is stripped from Phoenix, keeping a distribution similar to that of the observed H I cloud. Both in the SNe ejection case and in the ram pressure sweeping scenario, the distances and relative velocities imply that the H I cloud is not gravitationally bound to Phoenix, since this would require a Phoenix total mass about an order of magnitude larger than its total estimated mass. Finally, we discuss the possibility that Phoenix may be a bound Milky Way satellite. The minimum required mass of the Milky Way for Phoenix to be bound is MMW(<450 kpc)>=1.2×1012 Msolar, which comfortably fits within most current estimates. Based on observations collected in visitor mode with the VLT UT1, Antu, at the European Southern Observatory, Chile.