Долгожданное производство Алексея Николаевича в офицеры произошло весной 1856 года, 11 мая. Производству в прапорщики способствовали хлопоты матери, друзей, да и сам Плещеев, почувствовав ухудшение здоровья, стал с конца 1855 года энергично хлопотать о «высочайшем» помиловании, стремясь теперь уже вырваться из крепости в Оренбург. Потому и в письмах этого периода он часто сетует на скуку, дикость, ограниченность офицеров-сослуживцев, интриги, сплетни в командных кругах. «Ради бога, Виктор Дезидерьевич, вытащите меня из этого омута, называемого Сыр-Дарьин-ской линией», — просит он своего покровителя, которому с горечью признается, что жизнь «гибнет бесплодно, гибнет без пользы и счастья» и что «за два месяца, проведенных где-нибудь в большом городе, Петербурге, например, где общественная жизнь, науки, искусства — все в полном развитии, блеске, — я отдал бы охотно остальную жизнь». О тяжелом состоянии духа говорит поэт и в стихотворении «Раздумье».
Вместе с получением офицерского чина прапорщика Плещеев переводится из форта Перовский в 3-й Оренбургский линейный батальон, расположенный в самом губернском городе. Выехав из крепости 14 июня, Плещеев только через месяц с небольшим прибыл на место. Теперь уже на положении полноправного члена общества мог он посещать кружок местной интеллигенции, группировавшейся непосредственно вокруг самого В. А. Перовского, удостоенного не так давно графского титула. Для упавшего духом, истерзанного унижениями и оскорблениями за пять с лишним лет солдатчины поэта такая перемена в жизни значила очень много. Возобновились встречи с В. В. Григорьевым, налаживались новые знакомства; особенно близко сошелся Плещеев с начинающим литератором С. Н. Федоровым, которого опекал потом всю жизнь, посвятил ему ряд произведений.
Летом 1856 года в Оренбурге остановился М. Л. Михайлов — поэт, публицист, возглавлявший по заданию морского министерства литературно-этнографическую экспедицию по Оренбургскому краю, и Плещеев устанавливает дружеские отношения со столичным литератором — одним из активных сотрудников «Современника», другом и сподвижником Некрасова, Чернышевского, Добролюбова, Шелгунова и других революционно настроенных деятелей культуры…
Но Оренбург встретил Плещеева не без горестей: скоропостижно скончалась еще в 1855 году Любовь Захаровна Дандевиль, к которой Алексей Николаевич испытывал самые нежные чувства, а В. Д. Дандевиль в чине полковника уезжает вскоре на постоянное жительство в Петербург — утрату этих друзей поэт переживал особенно тяжело. Здоровье самого Алексея Николаевича тоже оставляло желать лучшего, и он вскоре по возвращении в Оренбург стал хлопотать об увольнении с воинской службы, благо что заключение медицинской комиссии о нездоровье его было отправлено в высшие инстанции еще из форта Перовского. Осенью 1856 года Плещеев подает на имя императора прошение о дозволении ему по состоянию здоровья перейти на гражданскую службу. Генерал-губернатор Перовский это прошение поддерживает, и 17 ноября того же года Алексей Николаевич «увольняется из военной службы с переименованием в коллежские регистраторы и с дозволением перейти на гражданскую службу, кроме столиц».
Расставшись с опостылевшей казарменной обстановкой, Плещеев решил некоторое время отдохнуть в самом прямом смысле: он часто посещал званые вечера у «оренбургских аристократов», куда теперь его приглашают не без удовольствия (умен, образован, молод — прекрасный кандидат в мужья), а существование свое поддерживает уроками французского, русского языков в тех же домах. Атмосфера светского общества, конечно, не могла удовлетворить поэта.
писал он в одном из стихотворений.
Но что делать, коль судьба «привязала» его к Оренбургу?..
На одном из вечеров в доме дворянского собрания Алексей Николаевич знакомится с семнадцатилетней Еликонидой Александровной Рудневой — дочерью титулярного советника Александра Михайловича Руднева, служившего надзирателем при илецком соляном промысле (крепость Илецкая Защита). Еликонида Александровна, наездами бывавшая с родителями в Оренбурге, считалась одной из самых видных красавиц края. Красота ее пленила сердце тридцатидвухлетнего поэта: Алексей Николаевич твердо решает связать свою судьбу с судьбой Еликониды Александровны — тем более что уже давно мечтал о семейном уюте.