We report the first direct search for the Kaluza-Klein (KK) modes of Randall-Sundrum gravitons using dielectron, dimuon, and diphoton events observed with the D0 detector operating at the Fermilab Tevatron p Collider at =1.96 TeV. No evidence for resonant production of gravitons has been found in the data corresponding to an integrated luminosity of 260 pb-1. Lower limits on the mass of the first KK mode at the 95% C.L. have been set between 250 and 785 GeV, depending on its coupling to standard model particles.