The energy-zenith angular event distribution in a neutrino telescope provides a unique tool to determine at the same time the neutrino-nucleon cross section at extreme kinematical regions, and the high energy neutrino flux. By using a simple parametrization for fluxes and cross sections, we present a sensitivity analysis for the case of a km3 neutrino telescope. In particular, we consider the specific case of an under-water Mediterranean telescope placed at the NEMO site, although most of our results also apply to an under-ice detector such as IceCube. We determine the sensitivity to departures from standard values of the cross sections above 1 PeV which can be probed independently from an a-priori knowledge of the normalization and energy dependence of the flux. We also stress that the capability to tag downgoing neutrino showers in the PeV range against the cosmic ray induced background of penetrating muons appears to be a crucial requirement to derive meaningful constraints on the cross section.