The recent high-statistics high-energy atmospheric neutrino data collected by IceCube open a new window to probe new physics scenarios that are suppressed in lower energy neutrino experiments. In this paper we analyze the IceCube atmospheric neutrino data to constrain the Violation of Equivalence Principle (VEP) in the framework of three neutrinos with non-universal gravitational couplings. In this scenario the effect of VEP on neutrino oscillation probabilities can be parametrized by two parameters $Delta gamma_{21}equiv gamma_2-gamma_1$ and $Deltagamma_{31}equiv gamma_3-gamma_1$, where $gamma_i$s denote the coupling of neutrino mass eigenstates to gravitational field. By analyzing the latest muon-tracks data sets of IceCube-40 and IceCube-79, besides providing the 2D allowed regions in $(phiDeltagamma_{21},phiDeltagamma_{31})$ plane, we obtain the upper limits $|phiDeltagamma_{21}| < 9.1times 10^{-27}$ (at 90% C.L.) which improves the previous limit by $sim4$ orders of magnitude and $|phiDeltagamma_{31}| lesssim 6times 10^{-27}$ (at 90% C.L.) which improves the current limit by $sim1$ order of magnitude. Also we discuss in detail and analytically the effect of VEP on neutrino oscillation probabilities.