We present multi-wavelength observations of the unassociated gamma-ray source 3FGL J2039.6-5618 detected by the Fermi Large Area Telescope. The source gamma-ray properties suggest that it is a pulsar, most likely a millisecond pulsar, for which neither radio nor $\gamma$-ray pulsations have been detected yet. We observed 3FGL J2039.6-5618 with XMM-Newton and discovered several candidate X-ray counterparts within/close to the gamma-ray error box. The brightest of these X-ray sources is variable with a period of 0.2245$\pm$0.0081 d. Its X-ray spectrum can be described by a power law with photon index $\Gamma_X =1.36\pm0.09$, and hydrogen column density $N_{\rm H} < 4 \times 10^{20}$ cm$^{-2}$, which gives an unabsorbed 0.3--10 keV X-ray flux of $1.02 \times 10^{-13}$ erg cm$^{-2}$ s$^{-1}$. Observations with the Gamma-Ray Burst Optical/Near-Infrared Detector (GROND) discovered an optical counterpart to this X-ray source, with a time-average magnitude $g'\sim 19.5$. The counterpart features a flux modulation with a period of 0.22748$\pm$0.00043 d that coincides, within the errors, with that of the X-ray source, confirming the association based on the positional coincidence. We interpret the observed X-ray/optical periodicity as the orbital period of a close binary system where one of the two members is a neutron star. The light curve profile of the companion star, with two asymmetric peaks, suggests that the optical emission comes from two regions at different temperatures on its tidally-distorted surface. Based upon its X-ray and optical properties, we consider this source as the most likely X-ray counterpart to 3FGL J2039.6-5618, which we propose to be a new redback system.