Paweł Legendorf studiował na uniwersytetach w Lipsku i Rzymie. Był sekretarzem kolejnych papieży – Mikołaja V i Kaliksta III. W 1458 roku został mianowany przez Piusa II administratorem apostolskim diecezji warmińskiej. Poprzednim biskupem tej diecezji był Pius II tuż przed wyborem na papieża. Latem 1460 roku Legendorf przyjechał na Warmię jako pełnoprawny biskup warmiński. W porozumieniu z królem Kazimierzem Jagiellończykiem objął rządy w diecezji. Między Kazimierzem a Zakonem Krzyżackim toczyła się wówczas wojna trzynastoletnia. Legendorf początkowo zachowywał się neutralnie, lawirując między dwiema stronami.
W 1464 roku złożył przysięgę wierności królowi Kazimierzowi, a dwa lata później, krótko przed układami pokojowymi, wypowiedział wojnę zakonowi. Na rokowaniach był też zdecydowanym przeciwnikiem ustępstw wobec zakonu. Biskup był sygnatariuszem aktu pokoju toruńskiego, na mocy którego Warmia została przyłączona do Polski i objęta protekcją królewską.
21 września 1466 roku został konsekrowany w Toruniu przez arcybiskupa Jana Gruszczyńskiego, w obecności Kazimierza Jagiellończyka i Jana Długosza. Zmarł rok później, prawdopodobnie otruty przez Krzyżaków.