Общество связывало с Головниным ожидание серьезных перемен. Публике импонировало первое появление Головнина-министра не в мундире, а в штатском костюме. В этом увидели символ отречения от «старой сухой формалистики», «знак наступления новых времен». Сам Головнин стремился действовать, «следуя общему духу и смыслу преобразований, которые вводили законность взамен произвола, равенство перед законом вместо привилегий, свободу и простор вместо стеснений, гласность вместо прежней тайны». Однако очень скоро он столкнулся с непреодолимыми барьерами, и первый камень преткновения ждал его на пути к цензурной реформе. По установкам царя, она должна была сделать административный контроль над печатным словом более эффективным, ориентироваться на интересы государственной безопасности, которым, по мнению Александра II, серьезно угрожали претензии прессы.

Головнину предстояло подготовить такой проект цензурной реформы, который одновременно угождал бы требованиям императора и успокаивал общество реальными переменами к лучшему в делах печати. Поручив подготовку проекта нового закона учрежденной при его министерстве комиссии князя Д. А. Оболенского, Головнин избрал «либеральный способ действия». Смысл его разъяснил В. А. Цеэ, лицейский товарищ и соратник Головнина, занимавший тогда должность председателя Санкт-Петербургского цензурного комитета: «При всеобщем требовании отмены цензуры нельзя цензуре действовать на жандармском праве и грубом произволе. Надо, напротив, употреблять представителей умственной деятельности всего русского общества на защиту порядков, закона и самого правительства, а этой цели нельзя достигнуть без доверия литераторов, а доверие это приобретается… постепенно открытым, добросовестным, благородным способом действия». Следуя этому принципу, Головнин пригласил литераторов, редакторов периодических изданий высказаться в печати по вопросам цензурной реформы. Кроме того, он рассчитывал «смелым образом действия нескольких даровитых писателей в пользу религии, нравственности, законности и правительства» сбалансировать общественное мнение, создавая противовес «ложным теориям». Он даже вынужден был делать шаги назад: исполняя волю императора, рассылал грозные циркуляры цензорам с требованием усилить строгость цензуры, согласился на временное приостановление выпуска «Современника» и «Русского слова». И все это для того, чтобы оппонирующая власти журналистика «не спугнула» правительство своим радикализмом, что могло бы отрицательно сказаться на результатах реформы.

Только в одном случае Головнин изменил тактике балансирования, отказавшись подписать подготовленный комиссией Оболенского проект нового цензурного устава, куда были внесены нормы об административном преследовании прессы «вредного направления». В записке на Высочайшее имя Головнин уклончиво объяснил свой поступок тем, что в проекте он обнаружил недостатки, не раскрывая при этом их сути. Там же он просил императора освободить его от управления цензурным ведомством и получил согласие. 12 января 1863 года цензура была передана министру внутренних дел П. А. Валуеву.

Уступив в цензурных делах, Головнин сосредоточился на подготовке университетской и школьной реформ, чтобы здесь отстоять курс на либеральные преобразования. Университетский устав 1863 года серьезно менял статус высшей школы – сводились к минимуму властные полномочия попечителей учебных округов и министра, восстанавливалась выборность ректора и деканов. Значительно возрастала роль кафедр, расширялись преподавательские штаты, обеспечивалась материальная поддержка профессуры. Устав закреплял право университетов на издание без предварительной цензуры учебной литературы. Иностранная научная литература могла приобретаться также без вмешательства цензуры и без пошлины. Сторонник широких научных контактов с европейскими учеными, Головнин выделял из фондов министерства средства для пособий командируемым за границу лучшим выпускникам университетов.