Speleothems in the karst caves of South Korea, which receive many visitors, are losing their aesthetic appeal due to black coloring. Mineralogical, textural, and chemical analyses were conducted on the speleothems to discover the cause of the discoloration. An abrupt color change from the natural color seen in the inner zones to the black color of the outer zones suggests that pollution commenced just after the opening of caves to visitors, and has continued since then. The main mineral compositions of both the outer black and the inner layers are the same, but the concentration of non-carbonate carbon is much higher in the black layers than in the inner layers. Electron microscopy showed that chain-like agglomerates (ca. 0.2–1.1 μm diameter) of sub-micrometer carbon spheres (ca. 0.02–0.05 μm diameter) are absent from the inner layer but present in the black layer, as well as in the cave aerosol. On the basis of their sub-micrometer size, agglomeration pattern, and composition, the carbon spheres and their agglomerates are considered to originate mostly from automobile exhaust. They are presumed to have been carried into the caves by visitors from urban environments and then deposited on the surface of growing speleothems. Protection of speleothems from discoloration requires control of these fine anthropogenic aerosols.