The MAGIC telescopes, located at the Roque de los Muchachos Observatory (2200 a.s.l.) in the Canary Island of La Palma, can perform observations pointing directly the sea. This permits to search for signatures of air showers induced by tau neutrinos in the PeV-EeV energy range arising from the ocean. We have studied the MAGIC response to such events, employing Monte Carlo simulations of upward-going tau neutrino showers. The analysis of the simulated shower images shows that air showers induced by tau neutrinos can be discriminated from the background of very inclined hadronic showers. We have calculated the point source acceptance and the expected event rates, assuming an incoming tau neutrino flux consistent with IceCube measurements and for a sample of generic neutrino fluxes from photo-hadronic interactions in AGNs. Finally, we report our first results from the tau neutrino search with the MAGIC telescopes.