The Global Ozone Monitoring Instrument (GOME) was launched on European Space Agency's ERS-2 platform in April 1995. The GOME data processor (GDP) operational retrieval algorithm has generated total ozone columns since July 1995. In 2004 the GDP system was given a major upgrade to version 4.0, a new validation was performed, and the 10-year GOME level 1 data record was reprocessed. In two papers, we describe the GDP 4.0 retrieval algorithm and present an error budget and sensitivity analysis (paper 1) and validation of the GDP total ozone product and the overall accuracy of the entire GOME ozone record (paper 2). GDP 4.0 uses an optimized differential optical absorption spectroscopy (DOAS) algorithm, with air mass factor (AMF) conversions calculated using the radiative transfer code linearized discrete ordinate radiative transfer (LIDORT). AMF computation is based on the TOMS version 8 ozone profile climatology, classified by total column, and AMFs are adjusted iteratively to reflect the DOAS slant column result. GDP 4.0 has improved wavelength calibration and reference spectra and includes a new molecular Ring correction to deal with distortion of ozone absorption features due to inelastic rotational Raman scattering effects. Preprocessing for cloud parameter estimation in GDP 4.0 is done using two new cloud correction algorithms: OCRA and ROCINN. For clear and cloudy scenes the precision of the ozone column product is better than 2.4 and 3.3%, respectively, for solar zenith angles up to 80°. Comparisons with ground-based data are generally at the 1-1.5% level or better for all regions outside the poles.