Kaolinite is a difficult-to-float clay existing in coal slurries which negatively impacts coal flotation. A better understanding of its adsorption behavior would improve coal-slurry processing. Carbon impurities in the kaolinite can affect this behavior. The appearance and elemental surface composition of the carbon impurities precipitated by kaolinite oxidative treatment were microscopically analyzed, and their chemical speciation and relative C and O contents were probed. The mechanisms of adsorption on the main kaolinite cleavage planes ((001) and (001) surfaces) for two carbon-impurity structural models, a phenolic hydroxyl unit (Ph−OH) and carbon hydroxyl unit (C−OH), were considered using density functional theory methods. The carbon impurities consisted mainly of C and O, with C present mostly as C−C, C−H, and C−O species, and O existing mainly in −OH and C−O structures. Both Ph−OH and C−OH units adsorbed stably on the kaolinite (001) and (001) surfaces through hydrogen bonding between the hydroxyl groups and surfaces. A strong electrostatic attraction occurred between the Ph−OH benzene ring and kaolinite surfaces, whereas the carbon ring in C−OH did not interact with either surface. Finally, for both units, adsorption on the kaolinite (001) surface was more stable than on the (001) surface.