В апреле 1849 года в числе других петрашевцев Плещеев был арестован (его арестовали в Москве, откуда он, гостивший у родственников, переслал петербургским друзьям «Письмо Белинского к Гоголю» и некоторую другую запрещенную литературу) и почти восемь месяцев находился в Алексеевском равелине Петропавловской крепости. Приговоренный Военно-судной комиссией к смертной казни (в числе наиболее активных петрашевцев, среди которых был и Достоевский), замененной затем «во внимание к молодым летам» солдатчиной в Оренбургском корпусе, Плещеев 6 января 1850 года был определен на постоянное жительство в Уральск и зачислен рядовым 1-го линейного батальона. Наступила тягостная и однообразная казарменная служба, за время которой Плещеев, по его собственному признанию, «стихи писать давно отвык» и вообще в первые годы ссылки ничего, кроме писем, не писал. Единственная отрада той поры — дружеские отношения с польскими ссыльными революционерами С. Сераковским, Б. Залесским, Я. Станевичем и особенно — встреча осенью 1850 года с Т. Г. Шевченко, который в этот период отбывал солдатчину в Уральске. После отправки Шевченко в Новопетровское укрепление между русским и украинским поэтами завязывается переписка, перешедшая впоследствии (когда оба окажутся на воле) в тесное творческое сотрудничество — Плещеев одним из первых познакомил русского читателя со стихами из «захолявных» тетрадей кобзаря.
Через два с лишним года постылой муштры и шагистики Плещеев был переведен в Оренбург рядовым 3-го линейного батальона. Оренбургский период оказался для опального поэта благодаря хлопотам его матери менее тяжелым в сравнении с уральским: Плещеев стал получать увольнительные, был освобожден от несения караульной службы, получил возможность посещать дом военного губернатора, где познакомился и подружился с некоторыми представителями местной интеллигенции, офицерами, среди которых — крупный ориенталист, первый историк Средней Азии В. В. Григорьев, путешественник-исследователь среднеазиатского края А. И. Бутаков, А. М. Жемчужников — поэт, один из будущих авторов знаменитых «Сочинений Козьмы Пруткова». В Оренбурге, при добром участии и содействии одного из помощников губернатора, офицера по особым поручениям В. Д. Дандевиля и его жены, Плещеев снова вернулся к поэзии, написав 17 февраля 1853 года после многолетнего перерыва стихотворение «При посылке Рафаэлевой Мадонны».
Весной — летом 1853 года Плещеев участвует в трудном походе русского отряда на кокандскую крепость Ак-Мечеть (ныне г. Кзыл-Орда), а затем — в штурме крепости, за что был произведен в унтер-офицеры.
