A highly significant structure is observed in the $\Lambda_c^+K^-\pi^+\pi^+$ mass spectrum, where the $\Lambda_c^+$ baryon is reconstructed in the decay mode $pK^-\pi^+$. The structure is consistent with originating from a weakly decaying particle, identified as the doubly charmed baryon $\Xi_{cc}^{++}$. The difference between the masses of the $\Xi_{cc}^{++}$ and $\Lambda_c^+$ states is measured to be $1334.94 \pm 0.72 (\mathrm{stat}) \pm 0.27 (\mathrm{syst}~\mathrm{MeV}/c^2$, and the $\Xi_{cc}^{++}$ mass is then determined to be $3621.40 \pm 0.72 (\mathrm{stat}) \pm 0.27 (\mathrm{syst} \pm 0.14 \, (\Lambda_c^+)~\mathrm{MeV}/c^2$, where the last uncertainty is due to the limited knowledge of the $\Lambda_c^+$ mass. The state is observed in a sample of proton-proton collision data collected by the LHCb experiment at a center-of-mass energy of 13 TeV, corresponding to an integrated luminosity of 1.7 $\mathrm{fb}^{-1}$, and confirmed in an additional sample of data collected at 8 TeV.