In this work, the surface structure of CeO2/nitrogen-doped carbon composites was tuned by controlling the feeding order of cerium nitrate and melamine in their synthesis process. Upon the characterization by TEM, XRD, TG, Zeta potential, and N2 adsorption-desorption isotherms, the synthesized CeO2/N-doped carbon composites were confirmed to be mainly composed of CeO2 and a large amount of N-doped carbon with different structures. Interestingly, it was found that the feeding order had a great influence on the nitrogen content, CeO2 dispersion, surface charge distribution, pore structure as well as specific surface area of CeO2/N-doped carbon composites. Compared to the CeO2/N-doped carbon composites prepared first by adding melamine (MCe), the CeO2/N-doped carbon composites prepared first by adding cerium nitrate (CeM) in their synthesis process had a much higher nitrogen content, which promoted the CeO2 dispersion on N-doped carbon surface and led to the formation of a predominantly positively charged surface in this sample, despite their lower specific surface area and unfavorable pore structure. The removal of Congo red by adsorption was employed to investigate the correlation between the surface structure of adsorbents and their adsorption capacities. It was discovered that the pore structure and specific surface area of CeO2/N-doped carbon composites were not the predominant factors for the adsorption removal of Congo red. Since Congo red presented an anionic state in aqueous solution, the formed Congo red anions could adsorb onto the positively charged surface of the sample via an electrostatic adsorption interaction, achieving high efficient removal of Congo red from the dye waste solution. Therefore, CeM exhibited a higher removal efficiency of Congo red. The adsorption capacities of the CeO2/N-doped carbon composites were further investigated to reveal the effect of different adsorption conditions such as inorganic salt, Congo red concentration, pH value, adsorbent dosage, and adsorption temperature.