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 livetime significantly improves model independent limit
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 \times
10^{6}$ $-$ $6.3 \times 10^{9}$ GeV to a level of $E^2 \phi \leq 3.6 \times
10^{-8}$ ${\rm GeV cm^{-2} sec^{-1}sr^{-1}}$.
