В эти годы морское министерство страны возглавлял вице-адмирал Ямамото Гомбей, его заместителем был контр-адмирал Сайто, а подчинявшийся им директор бюро военного кораблестроения контр-адмирал Сасоу руководил проектированием и заказом новых кораблей. К большому удовлетворению англичан, японцы в последнее время разместившие ряд заказов на постройку кораблей во Франции, решили заказать оба корабля в Англии с учетом всего лучшего в части конструкции корпуса, распределения броневой защиты и вспомогательной артиллерии у британских прототипов "Роял Соверен" и "Ринаун". Но артиллерия главного калибра значительно от них отличалась: на "Роял Соверен" стояло 4 343-мм орудия, на "Ринаун" 4 254-мм. По этому параметру "Фудзи" ближе подходил к броненосцу "Маджестик", имея такие же закрытые грушевидной формы барбеты с установленными в них 305мм орудиями, но уже 40-калиберными против 35-калиберных на "Маджестик". Впоследствии такие орудия установили на более поздние британские броненосцы типа "Формидейбл". В нашей литературе корабль первоначально именовался "Фудзияма" ("Fusi-Yama") по имени священной японской горы.
Эскадренный броненосец "Фудзи" был заложен 1 августа 1894 г. по кораблестроительной программе 1893 г. в первую очередь для противодействия двум китайским броненосцам, упомянутым выше, на верфи фирмы "Теймз Айрон Уоркс" (Thames Iron Works Company) в Блекуолле (Blackwall) по проекту Д. Макроу (G.G. Mackrow). Его спустили на воду 31 марта 1896 г., и он вошел в строй 17 августа 1897 г. Как и однотипный "Яшима", строившийся параллельно на верфи Армстронга, к войне с Китаем он уже не успел, так как был заложен именно в тот день, когда она была объявлена. Но в его конструкцию постарались внести возможно допустимые изменения, учитывавшие ее результаты, в первую очередь от сражения при Ялу, и коснувшиеся артиллерии главного и среднего калибра и системы бронирования.
Первоначально на ранней стадии эскизных проработок предполагалось ограничиться водоизмещением броненосца всего в 8000 т, но затем оказалось, что построить удовлетворительный корабль при таком малом водоизмещении уже нельзя. Действительно, эта величина лишь ненамного превышала водоизмещение первоначальных вероятных противников "Тинг Иен" и "Чен Иен", хотя тогда уже стоило думать и о будущем.
После самых тщательных проработок приняли водоизмещение в 12450 т. Первоначально корабль проектировался со следующими данными: размерения: 112,8 х 22,3 х 7,9 м, водоизмещение 12250/12450 т. Броневой пояс толщиной от 457 мм, утоньшаясь к оконечностям до 406 мм, должен был прикрывать лишь центр корабля и иметь длину 69 м. Толщина брони барбетов башен проектировалась в 356 мм, а броневой палубы 63 мм. Машины должны были развивать 14000 л.с. и обеспечить 18-узловую скорость. Ожидалось, что стоимость каждого из двух броненосцев без вооружения обойдётся в 5000000 золотых рублей. Как окончание постройки,так и их вооружение планировалось к началу 1898 г., что и было выполнено.
Фактически главные размерения очень незначительно отличались от проектных: длина между перпендикулярами составила 114 м, по ватерлинии 118,8 м, наибольшая 122,6 м, ширина 22,4 м, осадка 8,08 м при нормальном запасе угля 700 т. Полный запас угля равнялся 1200 т, чего хватало на прохождение 4000 миль 10- узловым экономическим ходом (по другим данным, на 3000 миль). Запасы топлива были заметно меньше, чем на прототипах. Нормальное водоизмещение "Фудзи" составило 12320 т, полное 12649 т.
Корпус набирался из стали, а двойное дно поднималось вдоль бортов до броневого пояса, имея продольные крепления – стрингеры по всей длине корабля. 181 водонепроницаемый отсек обеспечивал его непотопляемость (из них 36 находилось в двойном дне, 70 под броневой палубой, а 18 – над ней в оконечностях, 29 на нижней палубе, 6 – в главной и 22 отсека в цитадели). Для повышения остойчивости на протяжении половины длины броненосца имелись боковые кили шириной 0,76 м. Стальной таран, находясь ниже ватерлинии на 3,96 м, выступал от носового перпендикуляра на 3,81 м.
Броненосец первым в японском флоте, в отличие от "Фусо" и "Чин Иен", уже изначально оснащался сетями противоторпедного заграждения, которые долго прожили на всех флотах. Например, только в середине 20-х годов японские линкоры типа "Фусо" при модернизации лишились этих "украшений".