Non-standard neutrino interactions (NSI) involved in neutrino propagation inside Earth matter could potentially alter atmospheric neutrino fluxes. In this work, we look at the impact of these NSI on the signal at the ICAL detector to be built at the India-based Neutrino Observatory (INO). We show how the sensitivity to the neutrino mass hierarchy of ICAL changes in the presence of NSI. The mass hierarchy sensitivity is shown to be rather sensitive to the NSI parameters $epsilon_{emu}$ and $epsilon_{etau}$, while the dependence on $epsilon_{mutau}$ and $epsilon_{tautau}$ is seen to be very mild, once the $chi^2$ is marginalised over oscillation and NSI parameters. If the NSI are large enough, the event spectrum at ICAL is expected to be altered and this can be used to discover new physics. We calculate the lower limit on NSI parameters above which ICAL could discover NSI at a given C.L. from 10 years of data. If NSI were too small, the null signal at ICAL can constrain the NSI parameters. We give upper limits on the NSI parameters at any given C.L. that one is expected to put from 10 years of running of ICAL. Finally, we give C.L. contours in the NSI parameter space that is expected to be still allowed from 10 years of running of the experiment.