Abstract: In models with Large Extra Dimensions the smallness of neutrino masses can be naturally explained by introducing gauge singlet fermions which propagate in the bulk. The Kaluza-Klein modes of these fermions appear as towers of sterile neutrino states on the brane. We study the phenomenological consequences of this picture for the high energy atmospheric neutrinos. For this purpose we construct a detailed equivalence between a model with large extra dimensions and a (3+n) scenario consisting of three active and n extra sterile neutrino states, which provides a clear intuitive understanding of Kaluza-Klein modes. Finally, we analyze the collected data of high energy atmospheric neutrinos by IceCube experiment and obtain bounds on the radius of extra dimensions.