  We present the first radial velocity measurement of the stellar component of
the Local Group dwarf galaxy Phoenix, using FORS1 at the VLT UT1 (ANTU)
telescope. From the spectra of 31 RGB stars, we derive an heliocentric optical
radial velocity of Phoenix Vo=-52 +/- 6 \kms. On the basis of this velocity,
and taking into account the results of a series of semi-analytical and
numerical simulations, we discuss the possible association of the HI clouds
observed in the Phoenix vicinity. We conclude that the characteristics of the
HI cloud with heliocentric velocity --23 \kms are consistent with this gas
having been associated with Phoenix in the past, and 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
SNe produced in that last event of star formation, and a ram-pressure stripping
scenario. Both in the SNe ejection case and in the ram-pressure sweeping
scenario, the distances and relative velocities imply that the HI 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 $M_{MW}(<450
{\rm kpc}) \ge 1.2 \times 10^{12}$ M$_{\odot}$ which comfortably fits within
most current estimates.
