We report the discovery of a very young high-mass X-ray binary (HMXB) system associated with the supernova remnant (SNR) MCSNRJ0513-6724 in the Large Magellanic Cloud (LMC), using XMM-Newton X-ray observations. The HMXB is located at the geometrical centre of extended soft X-ray emission, which we confirm as an SNR. The HMXB spectrum is consistent with an absorbed power law with spectral index ~1.6 and a luminosity of 7x10^{33} ergs/s (0.2--12 keV). Tentative X-ray pulsations are observed with a periodicity of 4.4 s and the OGLE I-band light curve of the optical counterpart from more than 17.5 years reveals a period of 2.2324\pm0.0003 d, which we interpret as the orbital period of the binary system. The X-ray spectrum of the SNR is consistent with non-equilibrium shock models as expected for young/less evolved SNRs. From the derived ionisation time scale we estimate the age of the SNR to be <6 kyr. The association of the HMXB with the SNR makes it the youngest HMXB, in the earliest evolutionary stage known to date. A HMXB as young as this can switch on as an accreting pulsar only when the spin period has reached a critical value. Under this assumption, we obtain an upper limit to the magnetic field of < 5x10^{11} G. This implies several interesting possibilities including magnetic field burial, possibly by an episode of post-supernova hyper-critical accretion. Since these fields are expected to diffuse out on a timescale of 10^{3}-10^{4} years, the discovery of a very young HMXB can provide us the unique opportunity to observe the evolution of the observable magnetic field for the first time in X-ray binaries.