В 1857 году в "Общезанимательном вестнике" появляются его первые оды Горация "К Хлое" и рассказ в стихах "Без дочери", затем в периодике начинают публиковаться рассказы "Не первый и не последний", "Любовь дворовых", "Погибшее, но милое создание", небольшие зарисовки, которые впоследствии составили циклы "Петербургские типы" и "Петербургские золотопромышленники".
Летом 1858 года В. Крестовский благодаря тому же учителю словесности В. Водовозову сближается с литературным кружком Л. Мея, где попадает под влияние такого авторитета, как Аполлон Григорьев, дружба с которым оказала большое влияние на формирование таланта и вкусов молодого беллетриста. В литературный кружок Л. Мея входили также литератор М. Загуляев, поэты Ф. Берг, Н. Кроль, К. Случевский, критик и редактор "Литературной газеты" В. Зотов. Современники единодушно отмечали особую благожелательность, царившую на литературных вечерах этого кружка, готовность каждого кружковца прийти на помощь другому. Именно здесь, и в первую очередь Л. Меем, было оценено дарование молодого В. Крестовского, который, по словам современника, "быстро вырабатывал в себе талант чтеца, чем был так известен впоследствии".
Именно под влиянием "последнего русского романтика" Ап. Григорьева, с его своеобразной идеологией "либерального народничества", В. Крестовским были сделаны зарисовки петербургских нравов, опубликованные в печати: "Фотографические карточки" и "Типы Петербурга". Это были как бы эскизы его будущего романа "Петербургские трущобы". В то же время уже на втором курсе университета В. Крестовский сближается с Михаилом Достоевским, а через него — с его знаменитым братом Федором Михайловичем, идеи которого он безоговорочно принял и в будущем остался им верен. Идея Ф. М. Достоевского, высказанная им в знаменитых "Бесах" о том, что "надо сначала перестать быть международной обшмыгой, стать русским прежде всего, а стать русским — значит перестать презирать народ свой, и, как только европеец увидит, что мы начали уважать народ наш и национальность нашу, так тотчас же он начнет нас самих уважать", была В. Крестовскому особенно близкой.
Оставив после двухлетнего пребывания Петербургский университет, Всеволод Крестовский начинает сотрудничество в журнале Ап. Григорьева "Русское слово", где в 1860 году появляются его повести "Пчельник" и "Сфинкс". Одновременно многие периодические издания публикуют его греческие переводы, оригинальные стихотворения, короткие рассказы и эскизы, так что уже к 1864 году молодой беллетрист получает известность среди столичной публики. Оценка его литературных произведений весьма полярна: от положительных рецензий до резко отрицательных, низводящих сочинения В. Крестовского в ранг "легковесных", "поверхностных". Как отмечал наиболее пристрастный из критиков, А. Скабичевский, "очевидно было, что плывя по течению, Крестовский не врезывался в него глубоко, а скользил по поверхности. Обо всех тревоживших в то время общество вопросах он судил с кондачка, придавая им вид беззаветной пошлости…" И тот же А. Скабичевский в своих "Литературных воспоминаниях" отмечал, что "как это ни странно, но я должен признаться, что первые семена свободомыслия посеял в меня автор "Панургова стада".