Prace nad oboma krążownikami prowadzone były równolegle w Stoczni Admiralicji w Petersburgu („Bajana” budowano na zakrytej pochylni stoczni). Budowę na pochylni rozpoczęto 2 sierpnia 1905 rokuS. Winogradow, A. Fiedieczkin, Bronienosnyj kriejsier „Bajan”..., s. 103.. Kontraktowy koszt budowy kadłuba „Bajana” miał wynieść 9 409 137 rubli, maszyn, wykonywanych przez Towarzystwo Zakładów Francusko-Rosyjskich – 3 035 000 rubli. Budowę prowadzono według otrzymywanych z Francji planów ulepszonego krążownika typu Bajan – „Admirała Makarowa”, lecz stocznia wprowadzała do nich drobne zmiany, częściowo z powodu braku szczegółowych rysunków wykonawczych.
Oficjalne położenie stępki i zarazem wodowanie „Bajana” miało miejsce 2 sierpnia 1907 roku (starego stylu)S. Winogradow, A. Fiedieczkin, Bronienosnyj kriejsier „Bajan”..., s. 107-109.. Gotowość obu okrętów przewidywano pierwotnie na wrzesień 1907 roku, ale ich ukończenie – zwłaszcza „Bajana”, znacznie się opóźniało, w dużej mierze z powodu opóźnień dostawy maszyn i pancerza. Dopiero w połowie 1910 roku zmontowano wieże artyleryjskie i w październiku okręt był gotowy do prób, które jednak przeniesiono na kolejny rok wobec zalodzenia. Zimą kończono wyposażanie okrętu w Kronsztadzie.