Узнав, что самозванец бежал в Рыльск, армия Мстиславского осадила город. Но было уже поздно. Во-первых, за день до того Отрепьев перебрался в хорошо укрепленный Путивль. А во-вторых, даже Рыльск царские войска взять не смогли. У мятежного воеводы Долгорукова имелось всего несколько казачьих и стрелецких сотен, но он сумел привлечь к обороне все население города. Жители были наслышаны о зверствах в Комарицкой волости и сражались с мужеством отчаяния. Две недели армия Мстиславского вела стрельбу из орудий, пытаясь поджечь деревянные стены. Безуспешно. Зато очень эффективен был огонь рыльских пушкарей. Выстрелы с городских стен мешали придвинуть войска вплотную к крепости. Вскоре начали сказываться трудности снабжения. Встав лагерем у Рыльска, армия оказалась в полукольце крепостей, занятых неприятелем. Сторонники Лжедмитрия удерживали на севере Кромы, на юге Путивль, на западе Чернигов. Их отряды отбивали обозы с воинскими припасами, препятствовали заготовке продовольствия и фуража.
Попытка штурма успехом не увенчалась. Тогда Мстиславский снял осаду и отступил к Севску. Однако стоило царским полкам отойти от Рыльска, как его жители произвели вылазку и разгромили оставленный в лагере арьергард. Известия об этом привели Годунова в ярость. Он направил в полки окольничего Петра Шереметева и главного дьяка Власьева. Им было велено «…пенять и распрашивать, для чего от Рыльска отошли». Ссылки на усталость ратников царя не убедили. Борис не хотел даже слышать о роспуске войск до весны.
Ограниченные в своих действиях, с одной стороны, требованием начальства, с другой — ропотом утомленных войной дворян, воеводы приняли логичное в той обстановке решение. Они сосредоточили войска под стенами крепости Кромы. Восставший гарнизон во главе Григорием Акинфиевым еще осенью 1604 года превратил ее в передовой форпост армии самозванца. После предпринятой Акинфиевым попытки взять Орел Годунов направил против Кром войска Шереметева. Гарнизону Кром пришлось туго, и он запросил у «царевича» подмоги. Мольба о помощи не осталась без ответа. К концу декабря 1604 года в крепость прорвались около 500 донских казаков атамана Корелы.
Правительственные войска тоже получили подкрепление. В январе 1605 года к Шереметеву из Мценска подошел отряд воеводы Щербатого. Прибыла осадная артиллерия: две большие мортиры и пушка. В феврале под Кромами появился отряд стольника Бутурлина. Однако взять крепость все никак не получалось. И тогда царь направил к ней всю армию Мстиславского. Это решение, вопреки мнению большинства историков, не было ни случайным, ни глупым. К 4 марта 1605 года, когда войска Мстиславского стали лагерем у Кром, восстание охватило большинство городов и крепостей юга России. В начале марта в Путивль, где находился самозванец, доставили пленных воевод из Оскола, Валуек, Воронежа, Царева-Борисова и Белгорода. Вскоре на сторону восставших перешли гарнизоны крепостей Елец и Ливны. Таким образом, район Кром превратился для царской армии в удобный плацдарм, позволяющий одновременно угрожать войскам самозванца, расположенным на юге и юго-западе. Отсюда Мстиславский, в случае необходимости, мог одинаково успешно действовать на обоих оперативных направлениях. И в то же время хорошая дорога через Орел и Тулу надежно связывала царскую армию с Москвой, откуда она могла беспрепятственно получать снабжение.
Вскоре отряд князя Барятинского доставил из Карачева собранную там осадную артиллерию, и главное сражение кампании вступило в решающую фазу. Кромы были относительно небольшой крепостью с дубовыми стенами, выстроенными за десять лет до начала осады. Главным ее преимуществом было исключительно выгодное расположение на местности. Крепость стояла на вершине холма возле реки. Через окружающие болота и камыши к Кромам вела единственная узкая дорожка. По мере того как весна вступала в свои права, возможностей двигаться вне этой тропинки становилось все меньше. Первый штурм царские воеводы провели еще до прибытия тяжелой артиллерии. Ночью пехотинцы боярина Салтыкова подобрались к стенам города и подожгли их. Руководивший обороной Карела принужден был отвести казаков в острог. Царские ратники подступили к его стенам, но тут выяснилось, что весь посад простреливается из цитадели. Штурмующие несли огромные потери от меткого огня донцов. Чтобы спасти своих людей от истребления, Салтыкову пришлось отступить в лагерь.