The XENON10 experiment at the Gran Sasso National Laboratory uses a 15 kg xenon dual phase time projection chamber (XeTPC) to search for dark matter weakly interacting massive particles (WIMPs). The detector measures simultaneously the scintillation and the ionization produced by radiation in pure liquid xenon, to discriminate signal from background down to 4.5 keV nuclear recoil energy. A blind analysis of 58.6 live days of data, acquired between October 6, 2006 and February 14, 2007, and using a fiducial mass of 5.4 kg, excludes previously unexplored parameter space, setting a new 90% C.L. upper limit for the WIMP-nucleon spin-independent cross-section of 8.8 x 10^{-44} cm^2 for a WIMP mass of 100 GeV/c^2, and 4.5 x 10^{-44} cm^2 for a WIMP mass of 30 GeV/c^2. This result further constrains predictions of supersymmetric models.