По выходе его из госпиталя один из членов того кружка прогрессивной молодежи, в котором бывал Левитов, военный врач Б. Н. Маляго приглашает Левитова на лето к себе. Здесь будущий писатель начинает работать над своим первым произведением (позднее названо «Типы и сцены сельской ярмарки»), В это же время он хлопочет о переходе в Московский университет.

Но осенью 1856 года Левитов был внезапно арестован и сослан в Вологду, а затем в глухой городок Шенкурск Архангельской губернии, где должен был отрабатывать казенную стипендию в качестве фельдшера. Арест и ссылка, причина которых до сих пор не установлена, «окончательно надломили, — по свидетельству сестры писателя, — его силы, испортили характер…» Оторванный от какой бы то ни было общественной жизни, молодой человек начинает в этой глуши пить, неоднократно его посещают мысли о самоубийстве. Однако и в то время Левитова не покидает тяга к литературному творчеству. В 1858 году, вскоре после его перевода из Шенкурска опять в Вологду, друзья его получают несколько глав очерков «Типы и сцены сельской ярмарки».

В августе 1859 года Левитов, оборванный, с ногами, стертыми до ран, приходит к сестре в Лебедянь. Это пешее путешествие, по свидетельству друга и биографа Левитова, писателя Ф. Д. Нефедова, потребовало «месяцев: чтобы не погибнуть с голода… он принужден был останавливаться в селениях, наниматься писать в волостных правлениях, получая за свой труд по полтиннику в неделю».

Отдохнув у сестры, писатель снова пешком, без каких бы то ни было средств отправляется в Москву. Но и здесь ему живется крайне тяжело: часто он не имеет даже крова над головой, ночует на постоялых дворах, в лодках, в пустой полицейской будке, а то и просто на Москворецкой набережной. Получив немного денег от сестры, он снимает комнату на Грачевке, где ютилась столичная голь и беднота, позднее нашедшая в Левитове своего талантливого бытописателя.