Rare specimens of Centropyxis aculeata (Ehrenberg, 1832), cf. Difflugia oblonga (Ehrenberg, 1832), Amphitrema flavum (Archer, 1869) and an unidentified spherical form (similar to a protozoan ‘cyst’ in van Hengstum et al., 2007) were observed in the palynological preparations of cutting samples from a drill-hole in southern Saudi Arabia. These thecamoebians were found in Cretaceous formations in association with typical Cretaceous spore, pollen and dinoflagellate cysts. Since the youngest rock formation in this drill-hole is of Cretaceous age, contamination due to caving from post-Cretaceous sediments is thus ruled out. Although the oldest record of thecamoebians comes from Neoproterozoic strata, their pre-Holocene occurrences are rare and patchy. Since many thecamoebian tests are autogenous and are made of acid-resistant proteinaceous material, they occur in the palynological preparations of fossil sediments. It is suggested that careful observation and search for thecamoebians in palynological slides could potentially lead to new discoveries of these microfossils from Phanerozoic sediments from all over the world.