Tethytheria z kolei razem z góralkami tworzą grupę Paenungulata. Jest to jeden z najmniej kontrowersyjnych kladów ssaków, potwierdzony morfologią i badaniami molekularnymi. Ostatni wspólny przodek wszystkich brzegowców jest odleglejszy niż w przypadku waleni czy płetwonogich, sądzi się jednak, że przystosowały się one do wodnego trybu życia w podobnym czasie.
Zapis kopalny thumb|left|200px|Prorastomus – wczesny, eoceński przedstawiciel brzegowców W zapisie kopalnym brzegowce po raz pierwszy pojawiły się we wczesnym eocenie. Do końca tej epoki zdążyły się już znacznie zróżnicować. Zamieszkiwały rzeki, estuaria, wody morskie w okolicy brzegu. Były w stanie się szybko rozprzestrzenić. Najbardziej prymitywny nazwany przedstawiciel grupy, Prorastomus, odnaleziony został na Jamajce; odkryta w Tunezji część skalista kości skroniowej żyjącego we wczesnym eocenie nienazwanego przedstawiciela brzegowców ma jeszcze bardziej prymitywną budowę od odpowiadających jej części kości skroniowych przedstawicieli rodziny Prorastomidae z Jamajki.