This paper presents a reliable and low complexity scheme for acquisition, tracking and frequency offset recovery for a DSP-based satellite CDMA modem. An analysis of the performance, in terms of false alarm probability, detection probability and mean acquisition time, is carried out as a function of the complexity and the level of interference. The proposed scheme, based on a dedicated frame format, appears able to cope with the DSP complexity constraint also for high levels of interference. A DSP implementation and numerical results, obtained by means of analytical evaluations and measurements on a real test-bed, are given.