Energy dispersive x-ray analysis, petrographic observations, x-ray diffraction, and electron microprobe analysis were the techniques used to examine samples of tesserae from the Paphos mosaics to determine their composition, structure, and the presence of deterioration products such as soluble salts and weathering crusts. Color changes in different parts of treated and untreated mosaics received particular attention. Results are presented for the stone tesserae and for selected mortar samples.