Его интерес к единственному выжившему ребенку мистера и миссис Кьюстис, Мэри Анне Рэндольф Кьюстис, возник довольно рано, несомненно, к моменту его первого отпуска из Вест-Пойнта в 1827 году, когда он так щегольски выглядел на домашних вечеринках в своей серой кадетской форме. В соответствии со стандартами того времени, дружба между Робертом и Мэри развивалась ледниковыми темпами - нет никаких свидетельств того, что с обеих сторон произошел переворот, - и только при самом тщательном наблюдении и сопровождении. Тем не менее, ни от кого не ускользнуло, что молодой лейтенант Ли проводил гораздо больше времени в Арлингтоне, чем где-либо еще, и что Мэри Кэстис всегда смущенно радовалась, когда он сходил с места. Они оба любили делать наброски, в чем Роберт был довольно искусным любителем. К моменту окончания его отпуска между ним и мисс Кэстис, возможно, установилось некое взаимопонимание: ничего неподобающего или обязывающего - оба они понимали, что необходимо получить благословение мистера Кэстиса, - но этого было достаточно, чтобы дать им обоим надежду на более близкие отношения в будущем.
Они представляли собой удивительно несовместимую пару. Роберт был чрезвычайно красив - товарищ-кадет назвал его "красавцем" без всякого намека на гомоэротизм, просто как констатация факта, - в то время как у Мэри был длинный, узкий нос и острый подбородок отца, а также намек на опущенный рот. Возможно, портрет, нарисованный с нее в юности, неумело или не совсем справедливо передает ее черты, а прическа того времени не делает ей одолжений, но это не изображение великой красавицы. Их характеры тоже не были идеально синхронизированы. Роберт был пунктуален до мелочей, неистово организован, тщательно планировал; Мэри была "рассеянной", небрежной, часто опаздывала и, несмотря на внимание матери и многочисленных рабынь-служанок, часто была "неопрятной". В начале жизни она стала глубоко религиозной, в том смысле, который мы сейчас называем евангелическим, в то время как религиозный интерес Роберта был на данный момент гораздо менее интенсивным и более обычным, как будто регулярное посещение церкви было всего лишь одним из требований офицера и джентльмена. Он был удивительно энергичным, спортивным и подтянутым, мог по многу часов в день ездить верхом в любую погоду. Она же была человеком замкнутым, подверженным приступам головокружения и обмороков и нуждающимся в отдыхе. Она была "хрупкой" и миниатюрной, он же был почти шести футов ростом и мощно сложен. Он был беден и привык обходиться своими силами, в то время как она была избалованным единственным ребенком богатых, снисходительных родителей и привыкла всегда добиваться своего.
Как обычно бывает, когда люди влюблены, они почувствовали, что идеально подходят друг другу.
Самое важное письмо в жизни Роберта как солдата было отправлено ему из Вашингтона 11 августа 1829 года с приказом "явиться к майору Сэмюэлю Бэбкоку из инженерного корпуса для прохождения службы на острове Кокспур, в реке Саванна, штат Джорджия" к середине ноября и подписью "К. Гратиот, бригадный генерал". Если Роберт и был разочарован, он никому не сказал о своих чувствах; но, как он наверняка знал, это было мрачное место, недалеко от острова, где был похоронен его отец, прибрежный остров, покрытый приливами и отливами, где инженерный корпус уже несколько лет пытался построить форт для защиты подходов к Саванне, и настолько страдал от жары, влажности, лихорадки и комаров, что в летние месяцы работы даже не пытались вести.