We propose to use carrier interferometry (CI) codes to reduce the complexity of the maximum-likelihood multiuser-detection (ML-MUD) receiver in MC-CDMA systems with carrier frequency offsets (CFOs). Complexity reduction is achieved by exploiting the sparsity of the cross-correlation matrix of CI codes. It is shown that, for a fully-loaded MC-CDMA with spread gain N over a multipath channel with length L, the complexity of the ML-MUD receiver grows exponentially with 2L-1 (instead of N), where L ≪ N in a typical setting. Moreover, an upper bound for the minimum error probability is derived. Finally, simulation results are given to corroborate theoretical results.