In this Letter we report a spectroscopic confirmation of the association of HLX-1, the brightest ultra-luminous X-ray source, with the galaxy ESO 243-49. At the host galaxy distance of 95 Mpc, the maximum observed 0.2 - 10 keV luminosity is 1.2E42 erg/s. This luminosity is ~400 times above the Eddington limit for a 20 Msun black hole, and has been interpreted as implying an accreting intermediate mass black hole with a mass in excess of 500 Msun (assuming the luminosity is a factor of 10 above the Eddington value). However, a number of other ultra-luminous X-ray sources have been later identified as background active galaxies or foreground sources. It has recently been claimed that HLX-1 could be a quiescent neutron star X-ray binary at a Galactic distance of only 2.5 kpc, so a definitive association with the host galaxy is crucial in order to confirm the nature of the object. Here we report the detection of the Halpha emission line for the recently identified optical counterpart at a redshift consistent with that of ESO 243-49. This finding definitively places HLX-1 inside ESO 243-49, confirming the extreme maximum luminosity and strengthening the case for it containing an accreting intermediate mass black hole of more than 500 Msun.