Oleg was laid down at the Admiralty Shipyards at St. Petersburg on 6 July 1902, launched on 14 August 1903 and commissioned into the Russian Baltic Fleet on 24 June 1904. With the Russo-Japanese War already in progress, she was seconded to the Russian Second Pacific Squadron.

Under the command of Admiral Oskar Enkvist, Oleg was part of the Russian Second Pacific Squadron, which sailed from the Baltic Sea around the world to relieve the Japanese blockade of the Russian Pacific Fleet at Port Arthur during the Russo-Japanese War. The squadron engaged Japanese Admiral Togo Heihachiro's Combined Fleet at the Battle of Tsushima on 15 May 1905. During the battle, Oleg was damaged, but managed to escape and, together with the cruisers Aurora and Zhemchug reached the protection of the neutral port of Manila, where she was interned to the end of the war. After returning to the Russian Baltic Fleet, Oleg was refit and her torpedo nets removed. She was available for active service again from 17 October 1908.

At the start of World War I, Oleg was part of the Russian 1st Cruiser Brigade in the Baltic Sea. On 26 August 1914, together with sister ship Bogatyr, she covered minelaying operations in the Baltic, as well as laying mines herself. Mines laid by Oleg are credited with sinking the German light cruiser SMS Augsburg off Bornholm. (Augsburg was only damaged, not sunk MWP.) On 2 July 1915, Oleg participated in the Battle of Åland Islands during which she assisted in driving the German light cruiser SMS Albatross onto the beach. In June 1916, the Russian Baltic Fleet launched a major offensive against German convoys off the Swedish cost, near Gotland.

During the October Revolution of 1917, the crew of Oleg quickly declared support for the Bolshevik cause. The Treaty of Brest-Litovsk required the Soviets to evacuate their base at Helsinki in March 1918 or have their ships interned by newly independent Finland even though the Gulf of Finland was still frozen over. Oleg sailed to Kronstadt in what became known as the 'Ice Voyage'. In November 1918, Oleg and Bogatyr participated in the aborted invasion of Estonia by the Red Army. Oleg was torpedoed and sunk on the night of 17 June 1919 by Royal Navy speedboat CMB-4 commanded by Captain Augustus Agar in an attack on the Red Navy facilities at Kronstadt. Parts of the ship were salvaged in 1919 and 1933, and the rest of hulk was raised and scrapped in 1938.