Po pracach przygotowawczych stępkę pod budowę położono na pochylni faktycznie w lipcu 1896 roku. „Pałłada” była budowana w dużej kamiennej pochylni stoczni Galernyj Ostrowok. Jej budową kierował starszy budowniczy okrętów (odpowiednik pułkownika) P. Andriuszenko, a na późniejszym etapie młodszy budowniczy okrętów A. Mustafin, kierujący już budową „Diany”. Przed etapem prób zastąpił go z kolei N. Titow. Oficjalne uroczyste położenie stępki z udziałem generał-admirała Aleksego, połączone z przytwierdzeniem okolicznościowej srebrnej deski, miało jednak miejsce na wszystkich trzech okrętach dopiero roku, gdy budowa była zaawansowana. „Pałładę” zwodowano jako pierwszą roku, w obecności cara Mikołaja II.
Wyposażanie okrętu trwało długo, co spowodowane było w głównej mierze przez złą organizację robót i opóźnienia poddostawców, a także opóźnienia stoczni w montażu już przygotowanych elementów (jak np. maszyny sterowej). Działa kalibru 75 mm wyprodukowane pierwotnie dla „Pałłady” trafiły z wyjątkiem dwóch ostatecznie na wykańczany szybciej pancernik „Pierieswiet”, wobec czego należało wyprodukować kolejne. Planowano nawet rozpocząć próby bez kompletnego wyposażenia w kwietniu, a następnie wrześniu 1900 roku, ale okręt nie nadawał się do wyjścia w morze w tym czasie. W połowie 1900 roku przeprowadzono jedynie próby na uwięzi.