圣保罗教堂建于1521年，与圣保罗城堡一同由葡萄牙人建造，是欧洲人在东南亚修建的最古老教堂。因为著名传教士圣方济埋葬于此，所以教堂前竖立有圣方济神父的雕像。雕像全身为白色，雕刻得非常逼真，但是唯独没有右手。相传荷兰人不相信这位葡萄牙传教士死后肉身不败，所以将他的尸体挖出斩断其右手， 结果血流如注。惊恐的荷兰人因此将他视为神圣，在教堂前为他立像。每到周末，马六甲的荷兰后裔都会来此拜祭他。

教堂位于高地，所以荷兰人占领马六甲后，将教堂做为城堡。经过战争的圣保罗教堂断瓦残垣，外墙上留有很多弹孔，连屋顶都在战争中被炸烂。所以荷兰人另建教堂，圣保罗教堂则变成荷兰贵族的墓地，现在教堂内竖立的一块块写有拉丁文和葡萄牙文的石板，是当年贵族们的墓碑。