St. Paul´s Church neboli kostel sv. Pavla patří k dalším pozůstatkům portugalské vlády v malajské Melace. Kostel byl postaven v roce 1521 a přestavěn v roce 1566, čímž patří mezi nejstarší dochované kostely v Malajsii. Dnes z ní zůstala jen zřícenina, která stojí na vrcholu kopce svatého Pavla, v blízkosti pozůstatků tvrze A Famosa, se kterou společně se Stadthuys tvoří komplex Malackého muzea.
V roce 1548 založil sv. František Xaverský společně s Jezuity školu v prostorách kaple, známé jako St. Paul´s College, jež je považována za první školu moderního typu v Malajsii.
František Xaverský využíval kostel jako základnu pro jeho misionářské cesty do Číny a Japonska, které se mu staly roku 1552 osudným. O rok později bylo jeho tělo převezeno zpět do kostela a zde také spáleno a uloženo.