The first megaspores recovered from Ukrainian Lower Cretaceous strata are described and illustrated by reflected light and scanning electron micrography. Four lycopsid megaspore taxa are identified in core samples from north of Kherson (Khersons'ka Oblast), in the Black Sea Basin, southern Ukraine. Miospore assemblages recovered from the same samples reveal a slightly higher diversity of lycopsid microspores and, in conjunction with previous foraminiferal biostratigraphy, indicate an Aptian-Albian age for the strata. The megaspore suite shares genera with mid-Mesozoic assemblages from widely distributed parts of the world, but most of the Ukrainian specimens have subtle morphological differences from congeneric forms established in other regions. The megaspores accumulated in fluvial floodplain facies and highlight the potential of this region for investigating other Cretaceous mesofossils including early flowers.