Ф. Козлов развернул активную деятельность по выполнению требований, изложенных в письме ЦК КПСС к партийным организациям «Об усилении политической работы партийных организаций в массах и пресечении вылазок антисоветских, враждебных элементов» от 19 декабря 1956 г. Он регулярно направлял в ЦК КПСС отчеты о лицах, исключенных из партии и комсомола и выселенных из Ленинграда, и требовал увеличить лимиты на выявление «врагов народа» среди руководителей всех уровней.
В декабре 1957 – марте 1958 г. Фрол Козлов занял пост Председателя Совета Министров РСФСР. Оставаясь сторонником репрессивных мер, именно он отменил публикацию материалов, реабилитирующих жертв политических процессов 1936 – 1938 гг., хотя документ уже был подписан Н. М. Шверником, А. Н. Шелепиным и Р. А. Руденко. В марте 1958 – мае 1960 г. он уже 1-й заместитель Председателя Совета Министров СССР, а в мае 1960 – ноябре 1964 г. – секретарь ЦК КПСС по оборонным вопросам. Здесь он проявил себя как не вполне дальновидный политик, усугубив многие разногласия, в том числе и со странами – членами СЭВ. При этом Фрол Романович активно вмешивался и во внутреннюю политику страны: возражал против «преждевременной» публикации материалов о репрессиях 1930-х гг., выступал против реабилитации Н. И. Бухарина и других деятелей партии и культуры. По словам современников, уже в то время он претендовал на главную роль в партии и стране, предлагая, например, А. И. Микояну «свести Хрущева на показную роль и все решать за его спиной».
По свидетельству А. И. Микояна, Н. С. Хрущев, уважая в Козлове хорошего хозяйственника, видел своего преемника только в нем. Фрол Романович же, по словам коллег, явно копировал Никиту Сергеевича даже в мелочах и соперничал с Н. Г. Игнатовым, тоже замахнувшимся на роль лидера. На XXII съезде КПСС в 1961 г. Фрол Козлов убедил главу государства преследовать не только «зарвавшегося» Н. Г. Игнатова, но и его протеже Е. А. Фурцеву и А. Б. Аристова, недавно появившихся в Секретариате Центрального комитета партии. Никита Сергеевич прислушался к этому совету и вывел Фурцеву и Аристова из состава Президиума ЦК.
В 1962 г. во время массовых беспорядков в Новочеркасске Ф. Р. Козлов и А. И. Микоян были направлены туда, причем именно Козлов явился сторонником жесткого подавления рабочего выступления. Впоследствии, уже в начале 1990-х гг., Военная прокуратура России признала Козлова виновным в несанкционированном применении оружия по отношению к мирной демонстрации. В ответ Фрол Романович оправдывался тем, что забастовщики могли взять приступом горком партии. В результате от полученных ранений, по ряду данных, в общей сложности пострадали около 100 человек, 16 из которых погибли. Впоследствии Военная прокуратура признала уголовное дело о событиях в Новочеркасске закрытым в связи со смертью основных фигурантов дела (Н. С. Хрущева, Ф. Р. Козлова, А. И. Микояна и др.).
После того как Хрущев отбыл на отдых в Крым, Козлов остался «исполняющим обязанности» и временно курировал внутреннюю и внешнюю политику страны. Он завизировал поздравления к 1-му Мая, опубликованные в газете «Правда», и при этом допустил несколько серьезных по тем временам идеологических ошибок в тексте. Противники Козлова не замедлили преподнести это главе государства как вопиющую халатность. С того времени его безграничная популярность у Хрущева заметно пошла на убыль.
По словам современников, Ф. Козлов был не слишком образован, но был самолюбив, изворотлив и склонен к хвастовству. В общении с вышестоящими функционерами и подчиненными не брезговал такими качествами, как лесть и высокомерие. Он всерьез считал себя единственным преемником Н. С. Хрущева и любил об этом намекнуть в узком кругу. Со временем всесильный временщик начал докучать не только коллегам-конкурентам, но и самому Никите Сергеевичу. Козлов неоднократно получал от Хрущева порицания в грубой форме, что переживал очень тяжело. Возможно, именно следствием этого стал перенесенный им в 1963 г. инсульт. В результате должность 2-го секретаря Центрального комитета партии перешла к Л. И. Брежневу.
Отправленный в середине ноября 1964 г. в отставку «по состоянию здоровья» Фрол Козлов стал персональным пенсионером союзного значения. К тому моменту он имел звание Героя Соцтруда, был удостоен 4 орденов Ленина и 2 орденов Трудового Красного Знамени, орденов Отечественной войны 2-й степени и Красной Звезды. Скончался Фрол Романович Козлов 30 января 1965 г. и был похоронен в Кремлевской стене на Красной площади в Москве.