The church is consecrated to Santa María de la Palma (Mary the Virgin of Palm Sunday) since Palm Sunday 1344 when Alfonso XI of Castile conquered the city after the Siege of Algeciras (1342-1344).

Work began on the current building in 1723 when, as a result of population growth, the nearby Chapel of Our Lady of Europe no longer provided sufficient space for the congregation.

According to Pascual Madoz in his Gazetteer of 1843, "the church was completed in 1738 with alms from the faithful and other resources, allowing Bishop Lorenzo Armengual de la Mota on June 6 of that year, to give it the status of parish church which until then had been enjoyed by the primitive chapel of the Cortijo de Gálvez."

The main features of the facade are buttresses on either side of the door and a niche for the Virgin Mary.

Inside there is an 18th-century Italian alabaster sculpture which, according to legend, was taken from a boat that was prevented from leaving the port by bad weather.