A detailed palynological investigation of the almost continuous middle through upper Miocene sediment sequence of ODP Hole 907A in the Iceland Sea revealed the presence of a new species of the dinoflagellate cyst genus Batiacasphaera, and a new species of the acritarch genus Lavradosphaera. Batiacasphaera bergenensis sp. nov. and Lavradosphaera elongata sp. nov. are both morphologically distinctive and have well-defined stratigraphic range tops that are independently constrained by the pristine paleomagnetic record of Hole 907A. Both species disappeared within a narrow interval across the middle to late Miocene boundary, when small-scale glaciations on Greenland were large enough to reach sea level. The distinct morphology of the proposed species and their highest occurrence in this critical interval highlights their potential for future biostratigraphic application in the Miocene of the high northern latitudes, an area important for understanding the Late Cenozoic transition into a bipolar glaciated world.