Abstract: 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(tau tau)) and (epsilon(mu mu) – epsilon(tau tau)) 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(e mu), phi(e tau) 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.