We report the discovery of extended radio emission in the Phoenix cluster (SPT-CL J2344-4243, z=0.596) with the GMRT at 610 MHz. The diffuse emission extends over a region of at least 400-500 kpc and surrounds the central radio source of the Brightest Cluster Galaxy, but does not appear to be directly associated with it. We classify the diffuse emission as a radio mini-halo, making it the currently most distant mini-halo known. Radio mini-halos have been explained by synchrotron emitting particles re-accelerated via turbulence, possibly induced by gas sloshing generated from a minor merger event. Chandra observations show a non-concentric X-ray surface brightness distribution, which is consistent with this sloshing interpretation. The mini-halo has a flux density of $17pm5$ mJy, resulting in a 1.4 GHz radio power of ($10.4pm3.5) times 10^{24}$ W Hz$^{-1}$. The combined cluster emission, which includes the central compact radio source, is also detected in a shallow GMRT 156 MHz observation and together with the 610 MHz data we compute a spectral index of $-0.84pm0.12$ for the overall cluster radio emission. Given that mini-halos typically have steeper radio spectra than cluster radio galaxies, this spectral index should be taken as an upper limit for the mini-halo.