Petroleum waxes (PWs) are recognized as ubiquitously emerging marine pollutants. However, knowledge on their occurrence, particularly as persistent floaters of small size (<5 mm) in marine surface water, is scarce. For this study, 24 samples were collected in the North Sea by net-sampling (100 μm-mesh). Particles of wax-like appearance were detected at 14 stations. Similar appearing PWs from six stations with highest abundances were pooled per station and analyzed by ATR-FTIR (Attenuated total reflectance Fourier-transform infrared spectroscopy) and gas chromatography. Samples contained paraffin particles, being partly accompanied by substances like fatty acids and fatty alcohols. Using both analytical techniques provided a reliable detection of PWs and more details on their chemical composition. Furthermore, exemplarily the presence of PWs of 20–500 μm size was proven by μFTIR imaging. This study gives valuable insights into PW pollution in the North Sea, emphasizing the need for harmonized detection methods, ideally accompanying microplastics monitoring.