The majority of 3G mobile phones have an integrated GPS chip enabling them to calculate a navigation solution. But to deliver continuous and accurate location information, the satellite tracking process has to be stable and reliable. This is still challenging, for example, in heavymultipath and non-line of sight (NLOS) environments. New families of Galileo and GPS navigation signals, such as Alternate Binary Offset Carrier (AltBOC), Composite Binary Offset Carrier (CBOC), and Time-Multiplex Binary Offset Carrier (TMBOC), will bring potential improvements in the pseudorange calculation, including more signal power, better multipath mitigation capabilities, and overall more robust navigation. However, GNSS signal tracking strategies have to be more advanced in order to profit from the enhanced properties of the new signals.In this paper, a tracking algorithm designed for Galileo E1 CBOC signal that consists of two steps, coarse and fine, with different tracking parameters in each step, is presented and analyzed with respect to tracking accuracy, sensitivity and robustness. The aim of this paper is therefore to provide a full theoretical analysis of the proposed two-step tracking algorithm for Galileo E1 CBOC signals, as well as to confirm the results through simulations as well as using real Galileo satellite data.