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 pp(-) Collider at sqrt[s]=1.96 TeV. No evidence for resonant production of gravitons has been found in the data corresponding to an integrated luminosity of approximately equal to 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.