Ogon również przekształcił się w płetwę, a niektóre taksony rozwinęły również płetwę grzbietową.
Powstanie thumb|left|200px|Kladogram (na podstawie Spaulding, O'Leary, Gatesy, 2009) Nie ulega wątpliwości pochodzenie prawaleni od ssaków lądowych, różne jednak podawano hipotezy mające umiejscowić ich przodka na drzewie rodowym ssaków: drapieżne przypominające niedźwiedzie, pływające z otwartym pyskiem – hipoteza Darwina, wyśmiana przez innych specjalistów Mesonychia parzystokopytne jako grupa siostrzana hipopotamowatych ostatni wspólny przodek waleni i parzystokopytnych jako grup siostrzanych, zwierzę przypominające niewielkiego, krępego kanczyla
Obecnie udało się osiągnąć pewien konsensus w tej sprawie. Wykonane w latach 90. XX wieku badania genetyczne wskazywały nie tylko na bliskie pokrewieństwo waleni i parzystokopytnych, na co wskazywały dane paleontologiczne, morfologiczne, embriologiczne i molekularne. Graur i Higgins oraz Irwin i Árnason w tym samym roku 1994 przedstawili dane gentyczne świadczące o bliższym pokrewieństwie waleni i hipopotamów niż hipopotamów i innych grup parzystokopytnych. W efekcie walenie uznano za grupę w obrębie parzystokopytnych, choć jej status pozostawał jeszcze kwestią dyskusji.