Уже в начале мая 1907 г. Совет министров разрешил Морскому министерству вносить ежегодно в свой бюджет по 31 млн. руб. на строительство линейных кораблей. 9 июня 1907 г. Николай II утвердил новый, уменьшенный вариант «малой программы», в которую входили два дредноута, а уже 12 июля 1907 г. она была вновь скорректирована царем до четырех линейных кораблей. Стоимость программы составляла 127 млн. руб. Вся вторая половина 1907 г., весь 1908 г. и часть 1909 г. пошли на преодоление сопротивления Государственной думы, не утверждавшей бюджет Морского министерства, и на реконструкцию судостроительных заводов для постройки дредноутов. Кроме этого, для определения наилучшего типа будущего линкора Морское министерство решило объявить широкий конкурс проектов с привлечением как русских так и зарубежных разработчиков. Все это отодвинуло начало строительства новых линкоров, и только 30 июня 1909 г. на казенных верфях в Петербурге были заложены четыре первых русских дредноута («Севастополь», «Петропавловск», «Полтава» и «Гангут»).
Руководимое МГШ Морское министерство прикладывало огромные усилия для ускорения постройки нового флота. Состав министерства был обновлен, аппарат реформирован и вся его деятельность со второй половины 1909 г. имела совершенно другой характер, чем прежде. Его достижения в особенности упрочились после назначения морским министром в апреле 1911 г. вице-адмирала И.К.Григоровича, пользовавшегося доверием и авторитетом в широких слоях общества, а также в Государственной думе, благодаря чему ему удавалось добиваться крупных ассигнований на восстановление морских сил.
Вскоре после закладки «севастополей» МГШ предложил новую судостроительную программу, охватывающую десятилетний срок с 1909 по 1919 г. Линейные силы для Балтийского моря были в ней представлены 8 линкорами и 4 линейными крейсерами. 3 августа 1909 г. этот проект стал предметом обсуждения на Особом совещании под председательством премьер-министра П.А.Столыпина, где программа МГШ встретила ряд возражений. Результатом стала переработка программы, которую МГШ представил вновь в ноябре. Число предполагавшихся к постройке линейных судов для Балтики осталось неизменным. Подробная пояснительная записка к программе была 24 февраля 1910 г. рассмотрена и одобрена Советом министров, и 25 марта утверждена царем, начертавшем резолюцию: «Согласен. Программу выполнить обязательно в 10-летний срок». Так были даны задания новой судостроительной программы, потребовавшей более года на прохождение всех ведомственных инстанций перед поступлением ее в Думу. Однако последняя, занятая другими вопросами, к рассмотрению ее в 1910 г. не приступала. Все внимание Думы в отношении развития морских сил России было поглощено сначала обсуждением и принятием морского бюджета на 1910 г., а затем рассмотрением и утверждением программы срочного усиления Черноморского флота новыми боевыми кораблями, в том числе тремя дредноутами.