We propose a novel Minimum Distance guided Genetic Algorithm (MDGA) for Multi-User Detection (MUD) in a synchronous Multi-Carrier Code Division Multiple Access (MC-CDMA) broadband wireless system. In contrast to conventional GAs, our MDGA exploits adequately the output from a bank of Matched Filters as guidance. It starts with a balanced ratio of exploration and exploitation which is maintained throughout the process. A novel replacement strategy is proposed which increases dramatically the convergence rate as compared to the conventional GAs. This allows us to use the simplest form of genetic operators to gain significant reduction in computational complexity as well as near-optimum results. The simulation results demonstrate that our scheme achieves 99.54% and 50+% reduction in computational complexity as compared to the MUD schemes using exhaustive search and conventional GA respectively.