Pyrodinium bahamense var. compressum (Pbc) is one of the causative species of Paralytic Shellfish Poisoning (PSP). Incidents of PSP and red tides caused by Pbc are increasing, as well as the geographic distribution of Pbc expanding in Southeast Asia, where it has recently occurred in several areas that previously have not experienced blooms, such as Ambon Bay and Lampung Bay in Indonesia. Five factors including anthropogenic activities, natural activities, visual realization with red tide discoloration, development of techniques like RNA sequence and ELISA toxin kits, and the establishment of a regular monitoring system have been suggested to have led to the increase in reports of dinoflagellate blooms. Occurrence of dinoflagellate cysts in sediments has been used as evidence to which species of vegetative cells occurred in the water column. In this study, the vertical distribution of dinoflagellate cysts in sediments was investigated to confirm the first occurrence of Pbc cysts and to examine the floral changes of dinoflagellate cysts in Ambon Bay and Hurun Bay, Indonesia. In Ambon Bay, Pbc cysts first occurred in ca. 1850 and the cysts were continuously observed since ca. 1870. In Hurun Bay, Pbc cysts were found at 50-52 cm depth, and also at 42-44 cm depth. Cysts of Pbc first occurred at least in 1883, using depositional age calculated from the historical eruption of Mt. Krakatau. Cysts of Pbc have continuously occurred since ca. 1910, and the cyst densities rapidly increased in ca. 1960. Based on these findings, we consider that anthropogenic activities such as ballast water and transportation of shellfish seeds probably did not cause the introduction of Pbc in both bays.