Members of the Candidate phylum Patescibacteria, also called Candidate Phyla Radiation (CPR), are described as ultramicrobacteria with limited metabolic capacities. Wide diversity and relative abundances up to 80% in anaerobic habitats, e.g., in groundwater or sediments are characteristic for Candidatus Patescibacteria. However, only few studies exist for marine surface water. Here, we report the presence of 40 patescibacterial candidate clades at air-sea interfaces, including the upper water layer, floating foams and the sea-surface microlayer (SML), a < 1 mm layer at the boundary between ocean and atmosphere. Particle-associated (>3 µm) and free-living (3–0.2 µm) samples were obtained from the Jade Bay, North Sea, and 16S rRNA (gene) amplicons were analyzed. Although the abundance of Cand. Patescibacteria representatives were relatively low (<1.3%), members of Cand. Kaiserbacteria and Cand. Gracilibacteria were found in all samples. This suggests profound aerotolerant capacities of these phylogenetic lineages at the air-sea interface. The presence of ultramicrobacteria in the >3 µm fraction implies adhesion to bigger aggregates, potentially in anoxic niches, and a symbiotic lifestyle. Due to their small sizes, Cand. Patescibacteria likely become aerosolized to the atmosphere and dispersed to land with possible implications for affecting microbial communities and associated processes in these ecosystems.