We explore the potential of several Neutrino Factory (NF) setups to constrain, discover and measure new physics effects due to Non-Standard Interactions (NSI) in propagation through Earth matter. We first study the impact of NSI in the measurement of $theta_{13}$: we find that these could be large due to strong correlations of $theta_{13}$ with NSI parameters in the golden channel, and the inclusion of a detector at the magic baseline is crucial in order to reduce them as much as possible. We present, then, the sensitivity of the considered NF setups to the NSI parameters, paying special attention to correlations arising between them and the standard oscillation parameters, when all NSI parameters are introduced at once. Off-diagonal NSI parameters could be tested down to the level of $10^{-3}$, whereas the diagonal combinations $(epsilon_{ee} - epsilon_{tautau})$ and $(epsilon_{mumu}-epsilon_{tautau})$ can be tested down to $10^{-1}$ and $10^{-2}$, respectively. The possibilities of observing CP violation in this context are also explored, by presenting a first scan of the CP discovery potential of the NF setups to the phases $phi_{emu}, phi_{etau}$ and $delta$. We study separately the case where CP violation comes only from non-standard sources, and the case where it is entangled with the standard source, $delta$. In case $delta$ turns out to be CP conserving, the interesting possibility of observing CP violation for reasonably small values of the NSI parameters emerges.