Огайо протянул свои пути до Фредерика, штат Мэриленд, и оттуда Ли впервые прокатился на поезде, хотя "вагоны [все еще] приходилось запрягать лошадьми на часть расстояния". С паровыми машинами Ли, конечно, уже был знаком, но железная дорога в то время была для Америки чем-то вроде новинки.

В одном Ли был твердо уверен: когда весной он вернется в Сент-Луис, то возьмет с собой Мэри. Судя по ее письмам друзьям после приезда, Ли было нелегко убедить ее покинуть Арлингтон и отправиться в этот, с точки зрения виргинского гранда, сырой, примитивный городок в дикой местности. Несмотря на это, Ли оставили свою дочь Мэри с бабушкой и дедушкой и отправились со своими двумя сыновьями Кустисом и Уильямом (которого всегда называли "Руни"), сопровождаемые рабыней по имени Китти, чтобы присматривать за ними, в путешествие, которое длилось почти пять недель и продлилось от Вашингтона до Балтимора и Филадельфии: затем на поезде в Гаррисбург, штат Пенсильвания; из Гаррисбурга в Питтсбург на лодке по каналу; затем вниз по реке Огайо, с остановками в Цинциннати и Луисвилле; и, наконец, вверх по Миссисипи из Каира в Сент-Луис. Ли хвастался, что мальчикам понравилось путешествие, что, вероятно, правда - что может быть более захватывающим для маленьких мальчиков, чем путешествие по железной дороге, каналу и пароходу? - и что Мэри провела большую часть путешествия, дремля; но поскольку он также упоминает "тесноту, давку и карабканье", можно предположить, что Мэри не была в таком восторге, как ее дети, и что дремота могла быть ее способом убежать от суеты путешествия и нежелательной компании незнакомцев. Почти десятилетие спустя, во время своего первого визита в Америку, Чарльз Диккенс, более бесстрашный путешественник, чем Мэри Ли, жаловался на плохие манеры за столом, жевание табака, постоянную возню и плевки своих попутчиков, а также на тесноту и отсутствие уединения в поездах и на речных пароходах и на универсальную западную привычку вступать в разговор с совершенно незнакомыми людьми, как будто они друзья на всю жизнь.

На протяжении всей их супружеской жизни Ли, как и многие другие мужья, в письмах старался подчеркнуть, что Мэри нравится их путешествие, хотя совершенно очевидно, что при удобном случае она предпочитала оставаться дома, в привычной обстановке и комфорте Арлингтона. Ее чувства к Сент-Луису не могли улучшиться после того, как они прибыли туда, обнаружив, что комнат, которые, как предполагал Ли, были сняты для них, не было, и тем более не могли улучшиться после того, как они узнали, что их мебель и домашние вещи, следовавшие за ними, были уничтожены, когда пароход, на котором их перевозили, взорвался (не такое уж редкое явление на ранних пароходах, поскольку американская страсть к скорости и конкуренции часто приводила к перегреву котлов). Они провели месяц в неудобных временных жилищах, прежде чем Ли удалось снять часть большого особняка, изначально построенного Уильямом Кларком из экспедиции Льюиса и Кларка, который Ли довольно дружелюбно разделили с Уильямом Бомонтом, армейским хирургом, и его семьей.

Сент-Луис ни в коем случае не был тяжелым местом службы, по армейскому выражению, фортом на границе, но даже Ли, который был равнодушен к неудобствам, жаловался на летнюю жару и на то, что улицы превращались в удушливые пыльные бури, когда дул ветер летом, были по щиколотку в грязи, когда шел дождь, и превращались в замерзшие колеи зимой, а Мэри писала домой, что ее "заживо пожирают мошки, потому что они густые, как рой пчел, каждый вечер". К счастью, ей нравилось общество семьи Бомонт, с которой они делили дом, и уютные вечера с гостями, когда "Таси" Бомонт, милая и забавная шестнадцатилетняя дочь доктора, играла на пианино, а Ли переворачивал для нее страницы; но вид трапперов, индейцев и азартных игроков на речных судах на улицах, какими бы экзотическими и красочными они ни были, похоже, не вызвал у нее особого интереса. Несмотря на свои особняки и светские претензии, Сент-Луис находился на окраине пограничной зоны и все еще оставался грубым, неспокойным местом.

Хотя семья Ли в конце концов приспособилась к жизни в Сент-Луисе, Мэри большую часть времени болела или, во всяком случае, страдала от того, что Ли называл либо "желчным приступом", либо "вялостью". Можно предположить, что причиной тому были частые беременности, тоска по дому, а также преобладающее медицинское невежество и ошибки того времени. Если читать между строк, кажется, что она рассматривала Миссури как своего рода вынужденную временную ссылку из дома в Вирджинии и не хотела или не чувствовала себя способной присматривать за мальчиками в тех редких случаях, когда Китти отсутствовала. Даже дома в Арлингтоне, в окружении слуг, Мэри жаловалась, что ее "детишки шкварчат", а с одним слугой, который присматривал за ними, их, должно быть, было труднее контролировать. Ее безразличие к тем обязанностям, которые в то время считались "женскими", - вести домашнее хозяйство, по крайней мере, наблюдать на расстоянии за приготовлением пищи и воспитанием детей - постоянно раздражало мужа, хотя он в основном маскировал свое неодобрение довольно принужденным добрым юмором.

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

В июле Ли наконец-то присвоили звание капитана, спустя десять лет после окончания Вест-Пойнта - долгое ожидание даже по тогдашним меркам, особенно учитывая его обязанности. В противовес этому скромному достижению его работа обязывала остаться в Сент-Луисе до зимы, поэтому они с Мэри пропустили традиционное празднование Рождества с ее родителями в Арлингтоне; это не могло быть легким для Мэри, которая придавала большое значение таким вещам - она впервые оказалась вдали от дома на Рождество. Кроме того, она снова была беременна, а в середине зимы лед на реке не позволял путешествовать на пароходе, а