The People of Gibraltar
1530s - San Sebastián y  Las Dos Angustias - Gibraltar

As a primary source for anything to do with Gibraltar’s old Spanish churches that have now long disappeared, Portillo (see LINK) takes some beating. La Ermita de San Sebastian, la Iglesia de Nuestra Señora de las Angustias and la Iglesia de las Angustias are no exception. 
En la Barcina estaba la ermita de San Sebastián muy antigua, parece fábrica de cristianos, aunque no la sacristía.
Portillo also more or less confirms that there were two churches in Gibraltar at the time which were called “Angustias” - one of them near the Puerto de Mar and within the Barcina, the other in the town itself.
Es cosa maravillosa ver la devoción que en esta Ciudad se tiene con Nuestra Señora la Virgen Madre de Dios, pues casi todos las Iglesias que en ella hay son de su advocación. . . 
En la Villa Vieja, Nuestra Señora de la Cabeza, en San Sebastián, Nuestra Señora de Clarines . . . En la Puerta de la Mar Nuestra Señora de las Angustias.

En la Ciudad Nuestra Señora del Rosario (see LINK) . . .  y de las Angustias . . . .

To the south or to the left on the map of  the Qasbah, Villa Vieja and la Barcina lies la Turba which Portillo refers to as "la Ciudad"    (1627 - Luis Bravo de Acuña - Adapted)  (See LINK)

It is decidedly odd that there should have been two churches with the same name but so it seems. To avoid confusion I will call the one near the Puerta de Mar Nuestra Señora de las Angustia, and the one in town Iglesia de las Angustias. Helpfully, Portillo describes the overall boundary of the parishes he was responsible for as a magistrate.
A el Jurado Alonso Hernández del Portillo con la gente de su Collación que era los de vecinos de la Barcina, Albacar y Villa Vieja, el Baluarte del Canuto, dicho ahora de San Sebastián y Puerta de Mar y de Tierra. 
It means that Portillo must have been quite familiar with both San Sebastian and the Ermita de Nuestra Señora de las Angustias - I am certain that he would have been a frequent visitor to both. His observation that the sacristy of San Sebastian was not of Christian origin suggests that at least that part of the church may have had Moorish origins - a mosque perhaps. 

Another point worth mentioning is that just as the Baluarte del Rosario and that of Santiago had taken their name from nearby churches it is quite possible that the same holds true of the Baluarte de San Sebastian.

By 1690 both Santiago and Angustias were still going strong. Bothnames are mentioned by R. P. F. Geronimo de la Concepción’s (see LINK) Orbe del Emporio, Cadiz Illustrada in a chapter on Gibraltar listing around 18 churches. Whether his reference to “las Angustias” can be interpreted as being two churches is debateable. 

Local Historian George Palao on the other hand seems uncertain as to the exact location of the town church and suggests that it might have been at the junction of City Mill Lane and Main Street - where the department store Emporium once stood.

Iglesia de las Angustias at the junction of City Mill Lane and Main Street (1970 -George Palao - Adapted)

Early 18th century plan showing junction of Main Street and City Mill Lane - I am not sure whether the building outlined in red was in fact la Iglesia de las Angustias but it certainly was once a church  - "Par . . " is "the Parade" today's Mackintosh Square     (1753 - J Montressor - detail - adapted) (See LINK)

He then ruins this rather nice suggestion by giving several other possible sites such as:
. . . .above the 1704 Town Square or Grand Casemates Square and Esplanade while others state that it stood near the South Mole. . . .  there really was another church in the actual Casemates Square . . . as well as smaller chapel above the Square . . . . 

“Smaller chapel above the Square . . .”  Casemates   (1970 - George Palao - Adapted)
 . . . a very tiny chapel whose name is unknown which once stood at the junction of Engineers Lane (Calle del Gobernador) - and Main Street (Calle Real). (See LINK

“A very tiny chapel . . .     ”  (1970 -George Palao -Adapted)

To add to the general confusion, the Spanish historian Juan Manuel Ballesta Gómez in an article in the Campo historical magazine Almoraima 36 dated 2008 writes that:
Alonso Hernández del Portillo . . . muy meticuloso a la hora de describir . . . los establecimientos religiosos en su ciudad natal, no menciona los siguientes lugares de culto . . . probablemente por no existir ya o todavía durante su vida (1545?-1625?)  . . . . Ntra. Sra. de las Angustias. Ermita en el baluarte de San Pablo. . . . 
First of all while it might be true that that Portillo did not actually specify the exact site of the Angustias churches - he did in fact mention two of them - as quoted above. Secondly it seems much more likely that the church would have been built somewhere near San Pablo rather than on top of it. And finally perhaps it is worth remembering that the Baluarte de San Pablo which was also known during the 17th century as el Baluarte del Canuto or San Sebastian - was not all that far from the Puerta de Mar which is where Portillo sites one of the Angustias. 

To help anybody who has managed to plough through to the end of this article let me finish with a not particularly satisfying summary of most of the above comments.

Some researchers have opted for “the site of the “unknown church as an alternative site for the Iglesia de las Angustias - As far as I can make out it is impossible to tell which option is correct    (1627 - Luis Bravo de Acuña - Adapted)