Using fully self-consistent N-body models for the dynamical evolution of the Large Magellanic Cloud ( LMC ) in the Galaxy , we show that if the LMC initially has an extended old stellar halo before its commencement of tidal interaction with the Galaxy , physical properties of the stars stripped from the LMC stellar halo can have fossil information as to when and where the LMC was accreted onto the Galaxy for the first time . If the epoch of the first LMC accretion onto the Galaxy from outside its viriral radius is more than \sim 4 Gyr ago ( i.e. , at least two pericenter passages ) , the stars stripped from the stellar halo of the LMC can form an irregular polar ring or a thick disk with a size of \sim 100 kpc and rotational kinematics . On the other hand , if the LMC was first accreted onto the Galaxy quite recently ( \sim 2 Gyr ago ) , the stripped stars form shorter leading and trailing stellar stream at R = 50 - 120 kpc . Also distributions of the stripped stars in phase space between the two cases can be significantly different . The derived differences in structure and kinematics of the stripped stars therefore suggest that if we compare the observed three-dimensional ( 3D ) distribution and kinematics of the outer Galactic stellar halo along the polar-axis , then we can give strong constraints on the past orbit of the LMC . We also discuss whether the orbital properties of the LMC in successful formation models for the Magellanic Stream ( MS ) can be consistent with orbital properties of the LMC-type systems in Galaxy-type halos predicted from recent high-resolution cosmological simulations in a \Lambda CDM universe . We find that the orbital properties of the LMC in the successful formation models are consistent with those predicted from the cosmological simulations . We also find that the LMC can not merge with the Galaxy within the last \sim 6 Gyr in models consistent with predictions from the \Lambda CDM simulations . Given that the successful MS formation models predict at least two pericenter passages of the LMC in the Galaxy , we conclude that the LMC was accreted onto the Galaxy more than \sim 4 Gyr ago so that interaction between the LMC , the Small Magellanic Cloud ( SMC ) , and the Galaxy could form the MS and its Leading Arms ( LAs ) .