In this study, two new species of soft scale (Hemiptera: Coccomorpha: Coccidae) associated with rosemary, Rosmarinus officinalis L. (Lamiaceae) from Colombia, Cryptinglisia corpoica Kondo & Montes sp. nov. and Cryptinglisia ica Montes & Kondo sp. nov. are described and illustrated based on the adult female. Two other coccid species, namely Parasaissetia nigra (Nietner) and Saissetia coffeae (Walker), are newly recorded on rosemary. An identification key is presented to all species of soft scale that have been reported on Rosmarinus spp. An updated key to soft scale insects of the genus Cryptinglisia Cockerell is provided also.