Background Prophoca and Leptophoca represent the oldest known genera of phocine seals, dating from the latest early to middle Miocene. Originally, Prophoca rousseaui and Prophoca proxima were described based on fragmentary remains from the Miocene of Belgium. However, several researchers contested the union of Prophoca rousseaui and Prophoca proxima into one genus, without providing evidence. The stratigraphic context of Prophoca remained poorly constrained due to the lack of precise data associated with the original specimens collected in the area of Antwerp (north of Belgium). Methods Prophoca and Leptophoca are redescribed and their phylogenetic position among Phocidae is reassessed using PAUP. Dinoflagellate biostratigraphy has been carried out on sediment samples associated with specimens from Prophoca and Leptophoca to elucidate their approximate ages. Results Whereas the species Prophoca rousseaui is redescribed, Prophoca proxima is considered synonymous to Leptophoca lenis, with the proposal of a new combination Leptophoca proxima (Van Beneden, 1877). Sediment samples from specimens of both taxa have been dated to the late Langhian–early Serravallian (middle Miocene). Following a reinvestigation of Leptophoca amphiatlantica, characters from the original diagnosis are questioned and the specimens of Leptophoca amphiatlantica are considered Leptophoca cf. L. proxima. In a phylogenetic analysis, Prophoca rousseaui and Leptophoca proxima constitute early branching stem-phocines. Discussion Leptophoca proxima from the North Sea Basin is younger than the oldest known find of Leptophoca proxima from North America, which does not contradict the hypothesis that Phocinae originated along the east coast of North America during the late early Miocene, followed by dispersal to Europe shortly after. Morphological features of the appendicular skeleton indicate that Prophoca rousseaui and Leptophoca proxima have archaic locomotory modes, retaining a more prominent use of the fore flipper for aquatic propulsion than extant Phocidae.