Kołpaki wież artylerii głównej były grube na 152 mm, a pokład pancerny był gruby na 64 mm. Ze względu na solidniejszą konstrukcję, „Fuji” był uznawany za lepszy okręt od bliźniaczej „Yashimy”.

Budowa i służba „Fuji” otrzymał nazwę od góry Fudżi; został zamówiony w ramach programu rozbudowy floty na 1894 rok. Stępkę w stoczni Thames Iron Works w Blackwall (Londyn) położono 1 sierpnia 1894. Naczelnym projektantem okrętu był George Colby Mackrow. Pancernik zwodowano 31 marca 1896 i ukończono 17 sierpnia 1897. Pracę nadzorował zespół prawie 240 inżynierów i oficerów marynarki z Japonii, w tym przyszli premierzy Makoto Saitō i Tomosaburō Katō. W czasie prac wykończeniowych w Portland, okręt uczestniczył w paradzie morskiej z okazji Diamentowego Jubileuszu królowej Wiktorii 26 czerwca 1897 w Spithead, zanim wyruszył, przez Kanał Sueski do Japonii, do której dotarł przed lutym 1898.

W 1901 szesnaście armat kal. 47 mm zastąpiono taką samą liczbą dział 12-funtowych (76mm, QF 12 pounder 12 cwt), co spowodowało zwiększanie liczby załogi do 652, a następnie do 741 osób.