Как и «Падение Даира», повесть «Севастополь» основана на конкретном историческом материале — событиях, совершавшихся в период между февралем и октябрем 1917 года в Севастополе на Черноморском флоте, где Малышкин служил в это время младшим офицером одного из судов бригады траления.
Замысел повести «Севастополь» созрел у Малышкина к концу 1925 года. Весь 1926 год Малышкин прилежно работал над изучением и собиранием материала. В архиве писателя сохранились хронологические выписки, сведения об отдельных исторических лицах и другие заготовки. В беседе с корреспондентом газеты «Литературный Ленинград» Малышкин сказал: «Когда я в 16-м (очевидно, описка автора. — Л. В.) году пришел на военный корабль, я уже печатался… И вот на корабле я с самого начала стал вести дневники, зная, что эпоха эта исторична и рано или поздно мне придется воспользоваться моими записками. Но использовал их я только через 13 лет» («Литературный Ленинград», № 46(68) от 8 сентября 1934 г.). Неизвестно, насколько достоверна эта запись — дневники Малышкина нигде не обнаружены, но здесь особенно интересно свидетельство о стремлении писателя как можно правдивее и точнее передать описываемую эпоху.
Изучая события памятной ему эпохи, Малышкин одновременно намечает и типаж повести, составляет списки действующих лиц, причем в этих списках фигурируют и такие персонажи, которые в окончательный вариант повести не вошли.
Закончив подготовительную работу, Малышкин приступил к написанию самой повести. Работа шла споро, и уже 23 января 1927 года он сообщал своей родственнице К. Н. Кузовковой: «Милая Клавдия Николаевна, простите, что не сразу отвечаю. У меня была бешеная работа (своя), я ее заканчиваю, не разгибаясь работал все праздники, работал новый год и неделю спустя. Это — первая часть моего романа. Теперь она закончена и уже сдана. Будет напечатана в 8-й книге „Красной нови“. Заглавие — „Февральский снег“.
Вот теперь только поднял голову, свободно вздохнул и дал себе отдых на месяц. Впереди еще колоссальная работа.: надо написать еще две части (пока еще не начатые). Думаю закончить к 1928 году. Видите, какие масштабы!
Очень уж много времени отнимает обыденная работа — и мало остается для сердца. А эта вещь — как будто вылилась из сердца. Прочитаете — увидите». (Центральный государственный архив литературы и искусства.)
Работа над «Севастополем» продолжилась не до 1928 года, как первоначально предполагал писатель, а до 1931-го.
Первая часть повести была опубликована как самостоятельное произведение под названием «Февральский снег». («Красная новь», 1927, № 3.) Остальные части печатались в журнале «Новый мир» (1929, №№ 1, 2, 3, 1930, №№ 11, 12).
Корреспонденту газеты «Литературный Ленинград» Малышкин говорил: «Я еще не научился писать просто, хотя все время стремлюсь к сложному искусству простоты… Иногда мне кажется, что кое-что из написанного мною до читателя не дойдет. Но нет, встречи с читателями, беседы с ними убеждают меня в том, что читатели понимают даже сложные замыслы автора, а вкус читателя поражает своей правильностью». («Литературный Ленинград», № 46 (68) от 8 сентября 1934 г.) Читатели повести правильно поняли замысел автора — показать героя-интеллигента, порвавшего с прошлым, идущего за народом и с народом. Малышкин хотел усилить этот момент, ввести в повествование ряд эпизодов, показывающих, как «вели» Шелехова народные массы. Первоначально концовка повести мыслилась писателю так: после избрания Шелехова командиром отряда он «выводит отряд в предгорья — к подступам. Во флоте паника и гнев… Не Шелехов ведет, а в сущности его ведет отряд. На Крымской дороге перехватывают автомобиль с белыми летчиками из морской авиации. Их приводят к Шелехову. Он должен решить. Он должен дать приказание — убить. Он знает, что этого хочет масса и что она без него все равно сделает по-своему. Но приказание все же должен отдать он. Обреченные стоят перед ним — из того, старого мира. Он приказывает… Отряд и с ним Шелехов — идет дальше — в калединские степи». (А. Малышкин. Рассказы. М., 1931, стр. 41).
Писатель отверг этот вариант концовки, так как он противоречил всей логике развития образа Шелехова. По этому варианту получалось, что увлекаемый революционным коллективом Шелехов не ощущает себя его членом, вынужден подлаживаться, слепо идти за ним и поэтому не чувствует себя счастливым. В действительности же, слившись с массой, став командиром матросского отряда, он обрел наконец подлинное счастье.
Появление повести было встречено многочисленными отзывами и рецензиями, большинство из которых носило благожелательный характер.