Началась не менее продолжительная эпопея по достройке корабля. 10 октября 1907 года эскадренный броненосец «Андрей Первозванный» был переклассифицирован в линейный корабль. (В том же году англичане, введя в строй линейный корабль «Дредноут», совершили революцию в военном кораблестроении, сделав достройку «Андрей Первозванного» и «Павла I» бессмысленной, поскольку уже было совершенно ясно, что по окончании постройки эти корабли будут несколько превосходить по бронированию и вооружению английские броненосцы типа «Кинг Эдвард VII» постройки 1904 года и несколько уступать броненосцам типа «Лорд Нельсон» — последним английским додредноутам, введенным в строй на четыре года раньше «Андрея Первозванного». Но отступать было поздно. Разобрать корабли после четырехлетнего периода строительства, конца которому еще, правда, не было видно, никто не мог решиться).
Достройка «Андрея Первозванного» продолжалась. Ижорский завод поставлял броню, Обуховский — артиллерию, Франко Руи — машины, заграница — приборы и оборудование. В 1907 году в Морском министерстве подняли вопрос о выделении кораблестроительной части Санкт-Петербургского порта в самостоятельный судостроительный завод по образцу Балтийского. 5 января 1908 года по Высочайшему повелению, объявленному приказом по Морскому министерству, судостроительные верфи Нового Адмиралтейства и Галерного островка выделялись из состава порта, объединяясь под общим названием «Адмиралтейский судостроительный завод». В этот момент линкор «Андрей Первозванный» находился в состоянии готовности лишь на 69,06%, будучи в постройке уже пять лет. Лишь в 1910 году линейный корабль «Андрей Первозванный», перезимовав в Кронштадте, начал всесторонние испытания артиллерии, машин и прочих систем.
Испытания выявили недостатки всех систем корабля. Прогибалась палуба при бортовом залпе, садился пар — линкор не мог достигнуть проектной скорости, не удавалась наладка центральной наводки. Пролетел 1911 год, прошедший в испытаниях и переделках. Лишь 12 апреля 1912 года линейный корабль «Андрей Первозванный» был освящен и введен в строй, пробыв девять лет в стадии постройки и сдаточных испытаний. Сметная стоимость постройки «Андрея Первозванного» — 20 177 226 рублей (механизмы, изготовленные Франко-Русским заводом, — 3 560 000 рублей). Таким образом, общая сметная стоимость постройки линкора составила 23 737 206 рублей.
Еще до спуска командиром «Андрея Первозванного» был назначен капитан 1 ранга Руднев, шумно прославившийся как командир скандально-знаменитого крейсера «Варяг». Однако, герой Чемульпо, видимо, еще не совсем пришедший в себя от той славы, что обрушилась на него после гибели «Варяга», не смог организовать дисциплины и хода работ на «Андрее Первозванном» в тяжелом 1906 году, когда народ по традиции требовал у правительства отчета за проигранную войну, и был снят с должности. Достройкой и испытаниями линкора руководил капитан 1 ранга Шванк. После ввода «Андрея Первозванного» в строй командование линкором принял капитан 1 ранга Зеленой А. П.
Весь 1912 год на «Андрее Первозванном», несмотря на то, что он уже считался введенным в строй, продолжались испытания, сдаточные работы и различные переделки. Неожиданно выяснилось, что на линкоре никуда не годная система вентиляции, и санитарная служба флота потребовала ее замены. Менялось сетевое заграждение, устанавливались дополнительные броневые щиты для защиты от осколков компрессоров 12" и 6" орудий, укреплялись мамеринцы башен, улучшалась системы водоснабжения. Вместе с тем, на линкоре заканчивался начатый еще в 1911 году монтаж новой системы управления артиллерийским огнем, так называемой «совмещенной стрелки», предусматривающей управление огнем из боевого центрального поста с передачей туда приказов по переговорным трубам.
Зачисленный в состав бригады линейных кораблей «Андрей Первозванный» включился в боевую подготовку Балтийского флота в тот момент, когда все прочие оперативные помыслы были подчинены желанию остановить в случае войны прорыв немецкого флота в Финский залив на так называемой центральной минно-артиллерийской позиции. Все лето прошло в учениях на Балтике, а в начале сентября «Андрей Первозванный» в составе бригады линейных кораблей вместе с бригадой крейсеров и минными заградителями «Амур» и «Енисей» совершил поход в Копенгаген.
Зиму 1912-1913 гг. линкор провел в Гельсингфорсе. Зимой на корабле установили новые приборы для продувания каналов орудий главного калибра после выстрела, а также цилиндры из термоткани для прогревания орудий перед стрельбой в сильные морозы. Кроме того, практика показала, что в 8" башенных орудиях линкора заряжание вручную производится с большим успехом, нежели механическое. Система заряжания была переделана соответствующим образом, а высвободившиеся электромоторы было решено использовать для независимой подачи боезапаса в случае порчи зарядников.