We report the discovery of a massive, X-ray-luminous cluster of galaxies at z=1.393, the most distant X-ray-selected cluster found to date. XMMU J2235.3-2557 was serendipitously detected as an extended X-ray source in an archival XMM-Newton observation of NGC 7314. VLT-FORS2 R and z band snapshot imaging reveals an over-density of red galaxies in both angular and color spaces. The galaxy enhancement is coincident in the sky with the X-ray emission; the cluster red sequence at R-z ~ 2.1 identifies it as a high-redshift candidate. Subsequent VLT-FORS2 multi-object spectroscopy unambiguously confirms the presence of a massive cluster based on 12 concordant redshifts in the interval 1.38<z<1.40. The preliminary cluster velocity dispersion is 762+/-265 km/s. VLT-ISAAC Ks and J band images underscore the rich distribution of red galaxies associated with the cluster. Based on a 45 ks XMM-Newton observation, we find the cluster has an aperture-corrected, unabsorbed X-ray flux of f_X = (3.6 +/- 0.3) x 10^{-14} erg/cm^2/s, a rest-frame X-ray luminosity of L_X = (3.0 +/- 0.2) x 10^{44} h_70^{-2} erg/s (0.5--2.0 keV), and a temperature of kT=6.0 (+2.5, -1.8) keV. Though XMMU J2235.3-2557 is likely the first confirmed z>1 cluster found with XMM-Newton, the relative ease and efficiency of discovery demonstrates that it should be possible to build large samples of z>1 clusters through the joint use of X-ray and large, ground-based telescopes.