The first church is a small chapel built in 1521 by the Portuguese under the name of Our Lady of the Hill. The name of this church was changed to Annunciation church and Saint Paul church respectively and the church become larger and larger. When Dutch occupied Melaka, the church had become the Protestant church and they used this church until they built their own on the foot of the hill
The chapel was built from laterites. The church has a classic style pediment and a plain rose window in front. Within the structure is quite simple. On the floor, many grave plates can be found. This is the tradition of the Christians that will engrave the corpse on the church’s floor in order to be God’s servants.