We report on a search for extremely-high energy neutrinos with energies greater than 10(6) GeV using the data taken with the IceCube detector at the South Pole. The data was collected between April 2008 and May 2009 with the half-completed IceCube array. The absence of signal candidate events in the sample of 333.5 days of live time significantly improves model-independent limits from previous searches and allows to place a limit on the diffuse flux of cosmic neutrinos with an E-2 spectrum in the energy range 2.0 x 10(6) - 6.3 x 10(9) GeV to a level of E-2 phi <= 3.6 x 10(-8) GeV cm(-2) sec(-1) sr(-1).