Dmitri Donskoi, the Russian cruiser launched in 1883, is known to have sunk near Ulleung Island (East Sea, Korea) on May 29, 1905, while it was participating in the Russo-Japanese War. In order to find this ship, information about its possible location was obtained from Russian and Japanese maritime historical records. The supposed location of the ship was identified, and we conducted a five-year geophysical survey from 1999 to 2003. A reconnaissance three-dimensional topographic survey of the sea floor was carried out using multi-beam echo sounder, marine magnetometer, and side-scan sonar. An anomalous body identified through the initial reconnaissance survey was identified by a detailed survey using a remotely operated vehicle, deep-sea camera, and the mini-submarine Pathfinder. Interpretation of the acquired data showed that the ship is hanging on the side of a channel, at the bottom of the sea 400 m below sea level. The location is about 2 km from Port Jeodong, Uleung Island. We discovered 152 mm naval guns and other war materiel still attached to the hull of the ship. In addition, the remnants of the steering gear and other machinery that were burnt during the final action were found near the hull. Strong magnetic fields, resulting from the presence of volcanic rocks in the survey area, affected the resolution of the magnetic data gathered; as a result, we could not locate the ship reliably using the magnetic method. Severe sea floor topography in the gully around the hull gave rise to diffuse reflections in the side-scan sonar data, and this prevented us from identifying the anomalous body with the side-scan sonar technique. However, the sea-floor image obtained from the multi-bean echo sounder was very useful in verifying the location of the ship.