Wychowywał się na farmie koło Upperville w Wirginii i od małego uważał siebie za Wirgińczyka. 21 marca 1833 roku otrzymał nominację do West Point i zgłosił się do tej uczelni w czerwcu tego samego roku. Nauki jednak nie ukończył ze względu na słabe wyniki i problemy dyscyplinarne. Te drugie wynikały z incydentu, w którym rozbił talerz na głowie Jubala A. Early’ego. Uczelnię opuścił w 1836 roku.
Kariera wojskowa w US Army Pomimo nieukończenia West Point, jego ojciec i wuj ze strony matki, kongresmen Edward Stanly postarali się, aby uzyskał patent oficerski w stopniu podporucznika United States Army 10 lipca 1839 roku. Służbę rozpoczął w 6. Pułku Piechoty. Przez trzy lata służył na Florydzie podczas II wojny z Seminolami. W 1842 roku został przeniesiony na placówkę w Missouri. 30 marca 1844 roku został awansowany na porucznika. W tym samym roku ożenił się z Cecelią Lee Love, kuzynką Roberta E. Lee.
Walczył w wojnie amerykańsko-meksykańskiej z 6. Pułkiem Piechoty. W jej trakcie został ranny w bitwie pod Chapultepec (1847) oraz otrzymał dwa awanse brevet — wpierw na kapitana, a później, w uznaniu za męstwo, na majora.