После недолгого пребывания в Оренбурге весной 1854 года Плещеев снова возвращается в Ак-Мечеть, переименованную в форт Перовский (в честь оренбургского военного губернатора), и продолжает там службу до июня 1856 года, а затем переводится в Оренбург (теперь уже в звании прапорщика). Осенью того же года он подает прошение о дозволении ему по состоянию здоровья перейти на гражданскую службу, увольняется с военной и устраивается столоначальником Оренбургской пограничной комиссии.
Изменившиеся условия жизни (хотя за Плещеевым устанавливается секретный надзор, ему в 1857 году возвращается звание потомственного дворянина со всеми правами) дают возможность Плещееву приступить к интенсивной литературной деятельности. К поэзии, как уже было сказано, он вернулся еще в 1853 году. В годы военной службы в Ак-Мечети Плещеев много читает, следит за всеми литературными новинками, но пишет все же сравнительно мало. Теперь же, перейдя на гражданскую службу, имея достаточно свободного времени и установив связь с печатными органами столицы (с 1856 года с журналом «Русский вестник», а позднее, благодаря поэту М. Л. Михайлову, приезжавшему в 1856 году в Оренбург, с «Современником»), Плещеев помимо стихов обращается к беллетристике, создав именно в этот, оренбургский период наиболее значительные свои прозаические произведения — повести «Наследство», «Житейские сцены. Отец и дочь», «Пашинцев», «Две карьеры», рассказы «Буднев», «Неудавшаяся афера» и ряд других.
В конце 1857 года Плещеев женится, а весной следующего года выезжает в отпуск в Москву и Петербург, хлопочет о разрешении постоянно жить в одной из столиц. За время пребывания в Москве и Петербурге в 1858—1859 годах Плещеев завязывает многочисленные знакомства с литераторами, деятелями искусства, устанавливает добрые отношения с Чернышевским, Добролюбовым, Некрасовым. А в августе 1859 года он получает разрешение на постоянное жительство в Москве, куда вскоре и переезжает с семьей.
Поселившись в Москве, Плещеев поистине воспрянул духом, несмотря на определенные превратности судьбы (с него вплоть до 70-х годов не был снят секретный надзор),— недаром первые московские годы жизни он назовет лучшими. В этот период крепнут и расширяются литературные и общественные связи Плещеева: он избирается действительным членом Общества любителей российской словесности, становится соредактором газеты «Московский вестник», активно сотрудничает в крупнейших русских журналах и изданиях. Квартира поэта открыта для старых и новых друзей: здесь бывают А. Островский, Л. Толстой, Константин и Иван Аксаковы, заезжают Тургенев, Салтыков-Щедрин, Некрасов. Восстанавливает Алексей Николаевич дружеские отношения (на первых порах по переписке) с поселившимся в Петербурге после каторги и ссылки Достоевским.
