Paio Mendes (Latin: Pelagius, Spanish: Pelayo; died 1137) was the Archbishop of Braga from 1118 until his death. He was an adherent of the cause of Afonso Henriques, Count of Portugal.

In 1136 Paio attended the council of Burgos presided over by the legate Guido Pisano. At the council, he appears to have accepted the election as Bishop of Mondoñedo, one of his suffragan sees, of Pelayo, the candidate endorsed by Diego Gelmírez, Archbishop of Santiago de Compostela, in return for Diego's recognition of the Portuguese candidate, João Peculiar, as Bishop of Porto, a diocese over which he had up until then wielded much influence.^[1] Paio also witnessed the granting of an indulgence to the members of the Confraternity of Belchite.^[2]

On 4 July 1137 Afonso Henriques signed a treaty recognising himself as a vassal of Alfonso VII of León, a document to which Paio was a witness. The archbishop then remained with the Leonese court as it visited Santiago de Compostela, where he signed a royal charter. Before the end of October he was dead and succeeded by João Peculiar.^[1]