Cette église est la deuxième à avoir été appelée Sainte-Marie le Strand, la première ayant été située à un peu plus au sud. La date de sa fondation est incertaine, mais elle a été mentionnée dans un jugement de 1222, sous le nom d'Église des Innocents, ou Sainte-Marie et des Innocents. Elle a été démolie en 1549 par Edward Seymour, premier duc de Somerset, pour faire place à Somerset House. Une nouvelle église a été promise aux paroissiens, mais celle-ci n'a jamais été construite, ce qui les forçait à se déplacer à l'église voisine de St Clement Danes.
La nouvelle St. Mary Le Strand était le premier des cinquante nouvelles églises commanditées en 1711 à Londres. La construction a débuté en février 1714 sous la direction de l'architecte James Gibbs; c'était son premier grand projet à la suite de son retour d'Italie. Le clocher a été achevé en , l'église a été consacrée le .
Charles Édouard Stuart y aurait renoncé à sa foi catholique romaine dans cette église anglicane au cours d'une visite secrète à Londres en 1750.
Les parents de Charles Dickens, John Dickens et Elizabeth Barrow, s'y sont mariés en 1809.
L'église a échappé de justesse la destruction à deux reprises au cours du XXe siècle.
Au début du siècle, le London County Council a proposé de démolir l'église afin d'élargir le Strand, une campagne impliquant l'artiste Walter Crane a réussi à l'éviter, bien que le cimetière ait été rasé et les tombes déménagées au cimetière de Brookwood.
Le Blitz de Londres de la Seconde Guerre mondiale a causé des gros dommages au voisinage, mais à nouveau l'église évita la destruction, même si elle a été touchée par l'explosion d'une bombe à proximité.
James Gibbs a proposé que l'église devrait avoir une structure dans le style italien avec un petit campanile sur l'extrémité occidentale et sans une flèche. Au lieu, il y aurait une colonne de 76 mètres de haut, surmontée par une statue de la reine Anne, à l'ouest de l'église. Une grande quantité de pierre a été acheté et apporté au site, mais le plan a été abandonné après la mort de la reine en 1714. Au lieu, l'architecte a été commandé de ré-utiliser le pierre à édifier une flèche, qui a changé le plan de l'église fondamentalement.
.svg){kind=small}
