The MAGIC telescopes, located at the Roque de los Muchachos Observatory (2200 a.s.l.) in the Canary Island of La Palma,
are placed on the top of a mountain, from where a window of visibility of about 5 deg in zenith and 80 deg in azimuth is open in the direction of the surrounding ocean. This permits to search for a signature of particle showers induced by earth-skimming cosmic tau neutrinos in the PeV to EeV energy range arising from the ocean. We have studied the response of MAGIC to such events, employing Monte Carlo simulations of upward-going tau neutrino showers. The analysis of the shower images shows that air showers induced by tau neutrinos can be discriminated from the hadronic background coming from a similar direction. We have calculated the point source acceptance and the expected event rates, for a sample of generic neutrino fluxes from photo-hadronic interactions in AGNs. The analysis of about 30 hours of data taken toward the sea leads to a point source sensitivity for tau neutrinos at the level of the down-going point source analysis of the Pierre Auger Observatory, if the AUGER observation time is dedicated to a similar amount by MAGIC.