Pochodził z arystokratycznej rodziny, która cieszyła się wielką estymą w rodzimym stanie. Ojciec Roberta – Henry „Light Horse Harry” Lee – był bohaterem amerykańskiej wojny o niepodległość, podczas której w stopniu pułkownika dowodził kawalerią kontynentalną.
W 1825 roku Lee junior wstąpił do akademii wojskowej w West Point. Szkołę ukończył z drugim wynikiem na roku. Oddelegowany w stopniu podporucznika do korpusu inżynierskiego prowadził prace fortyfikacyjne na Wschodnim Wybrzeżu, m.in. przy budowie Fortu Pulaski w Savannah.
Rozkwit kariery wojskowej Lee nastąpił podczas wojny amerykańsko-meksykańskiej (1846 – 1847). Jako oficer sztabowy nie unikał pola walki, aktywnie uczestnicząc w największych bitwach kampanii. Trzykrotnie awansowany, ranny podczas szturmu na twierdzę Chapultepec, zakończył wojnę w randze pułkownika z opinią jednego z najzdolniejszych oficerów w armii. W latach 1852 – 1855 pełnił funkcję superintendenta w West Point – ten okres uznano za jeden z najlepszych w historii uczelni. Później objął dowództwo 2. Pułku Kawalerii, z którym wyjechał do Teksasu, by strzec bezpieczeństwa osadników.
Konflikt narastający między Północą i Południem rzucił go w wir wydarzeń w Harpers Ferry, gdzie zbuntowani abolicjoniści pod wodzą Johna Browna zajęli magazyny federalne. W październiku 1859 roku Lee powierzono zadanie przywrócenia spokoju w mieście i schwytania przywódców zamieszek. Na początku 1861 roku prezydent Lincoln zaproponował mu naczelne dowództwo nad armią federalną, która miała zmusić zbuntowane stany do powrotu na łono Unii. Lee wiedziony lokalnym patriotyzmem odmówił i oddał swe usługi władzom rodzimej Wirginii. Jego stosunek do wojny domowej najlepiej oddają słowa wypowiedziane do jednego z oficerów: „Nigdy nie podniósłbym ręki przeciw Unii, ale być może konieczne będzie, abym podniósł muszkiet w obronie mojego rodzinnego stanu – Wirginii”.
20 kwietnia 1861 roku, trzy dni po secesji Wirginii, Lee złożył rezygnację ze służby w armii federalnej. Mimo że kilka tygodni później otrzymał stopień generała Konfederacji, na kołnierzu pozostawił trzy pułkownikowskie gwiazdki odpowiadające jego ostatniej randze w armii Stanów Zjednoczonych. Przez całą wojnę nosił skromny szary mundur bez generalskich insygniów.
