Oldendorf absolvierte die Akademie der US Seestreitkräfte (US Naval Academy) im Jahr 1909 und diente anschließend auf verschiedenen Schiffen der US Navy.
1922 erhielt er sein erstes Kommando auf dem ZerstörerDecatur, das er bis 1927 behielt.
Oldendorf wechselte im Januar 1944 in den Pazifik und kommandierte dort die 4. Kreuzerdivision von der Louisville aus. Mit seinem Verband unterstützte er unter anderem die Landungsoperation auf den Marshallinseln.
Am 24. Oktober 1944 platzierte er seine Flotte aus Schlachtschiffen und Kreuzern in der klassischen Formation Crossing the T in der Straße von Surigao südwestlich von Leyte und besiegte damit die Japaner in der Schlacht in der Surigao-Straße. Er wurde daraufhin im Dezember 1944 zum Vice Admiral befördert.
Er trat 1948 im Rang eines Admirals aus dem aktiven Dienst zurück, nach ihm wurde der Zerstörer Oldendorf benannt.
Oldendorf starb am 27. April 1974 und wurde auf dem Nationalfriedhof Arlington beigesetzt.