Paolo Navigajoso (died 1277) was a scion of the noble Venetian Navigajoso family and third Latin ruler of the island of Lemnos in Greece.

Paolo was the eldest son and heir of Leonardo Navigajoso. Upon his father's death in 1260, he inherited one-half of Lemnos as well as the title megadux of the Latin Empire, which he continued to use even though the Latin Empire fell to the Empire of Nicaea in 1261. Along with his two brothers, Filippo and Nicolao, and his cousins, Giovanni Foscari and Filocalo Gradenigo, who controlled the other half of the island, he opposed the Byzantines when they attacked the island in 1276 under Licario. However, Licario persisted and gradually took the island as the Latin princes fell in battle one by one. Nevertheless, the main fortress of Kastro continued to resist, and after Paolo was killed in 1277, his widow, Maria Sanudo, a daughter of Angelo Sanudo, continued to defend it until she was eventually forced to surrender it in 1278.