The Fermi Large Area Telescope gamma-ray source 3FGL J2039.6-5618 contains a periodic optical and X-ray source that was predicted to be a 'redback' millisecond pulsar (MSP) binary system. However, the conclusive identification required the detection of pulsations from the putative MSP. To better constrain the orbital parameters for a directed search for gamma-ray pulsations, we obtained new optical light curves in 2017 and 2018, which revealed long-term variability from the companion star. The resulting orbital parameter constraints were used to perform a targeted gamma-ray pulsation search using the Einstein@Home-distributed volunteer computing system. This search discovered pulsations with a period of 2.65 ms, confirming the source as a binary MSP now known as PSR J2039-5617. Optical light-curve modelling is complicated, and likely biased, by asymmetric heating on the companion star and long-term variability, but we find an inclination i greater than or similar to 60 degrees, for a low pulsar mass between 1.1 M-circle dot < M-psr < 1.6 M-circle dot, and a companion mass of 0.15-0.22 M-circle dot, confirming the redback classification. Timing the gamma-ray pulsations also revealed significant variability in the orbital period, which we find to be consistent with quadrupole moment variations in the companion star, suggestive of convective activity. We also find that the pulsed flux is modulated at the orbital period, potentially due to inverse Compton scattering between high-energy leptons in the pulsar wind and the companion star's optical photon field.