We demonstrate the unique capabilities of Herschel to study very young luminous extragalactic young stellar objects (YSOs) by analyzing a central strip of the Large Magellanic Cloud obtained through the HERITAGE Science Demonstration Program. We combine PACS 100 and 160, and SPIRE 250, 350, and 500um photometry with 2MASS (1.25-2.17um) and Spitzer IRAC and MIPS (3.6-70um) to construct complete spectral energy distributions (SEDs) of compact sources. From these, we identify 207 candidate embedded YSOs in the observed region, ~40% never-before identified. We discuss their position in far-infrared color-magnitude space, comparing with previously studied, spectroscopically confirmed YSOs and maser emission. All have red colors indicating massive cool envelopes and great youth. We analyze four example YSOs, determining their physical properties by fitting their SEDs with radiative transfer models. Fitting full SEDs including the Herschel data requires us to increase the size and mass of envelopes included in the models. This implies higher accretion rates (greater or equal to 10^-4^M_{sun}_/yr), in agreement with previous outflow studies of high-mass protostars. Our results show that Herschel provides reliable longwave SEDs of large samples of high-mass YSOs; discovers the youngest YSOs whose SEDs peak in Herschel bands; and constrains the physical properties and evolutionary stages of YSOs more precisely than was previously possible.