Maximum likelihood (ML) joint detection of multi-carrier code division multiple access (MC-CDMA) systems can be efficiently implemented with a sphere decoding (SD) algorithm. In this paper, we examine the application of complex instead of real SD to detect MC-CDMA, which solves many problems in a more elegant manner and extends SD adaptability to any constellation. We first propose a new complex SD algorithm whose efficiency is based on not requiring an estimate of the initial search radius but selecting the Babai point as the initial sphere radius instead; also, efficient strategies regarding sorting the list of possible lattice points are applied. Indeed, complex SD allows complex matrix operations which are faster than real counterparts in double dimension. Next, a novel lattice representation for the MC-CDMA system is introduced, which allows optimum multiuser detection directly from the received signal. This avoids noise whitening operation, and also despreading and equalization procedures are not required further at the receiver side This work has been partly funded by the Spanish government with national project MACAWI (TEC 2005-07477-c02-02) and project MAMBO (UC3M-TEC-05-027)