The first post-reformation Catholic church was opened in Cambridge in 1841; St Andrew's Catholic Church (later dismantled and re-built in St Ives) remained the only chapel available for Cambridge Catholics until the construction of OLEM. In 1865, the parish priest Canon Thomas Quinlivan acquired additional adjacent land, but the funds could not be raised for construction. With the aid of the Duke of Norfolk, the entire Lensfield estate was purchased in 1879. The task of raising more funds fell to Quinlivan's successor, Mgr Christopher Scott. On the Feast of the Assumption, 1884, the former ballerina Yolande Lyne-Stephens, widow of Stephens Lyne-Stephens, reputed to be the richest commoner in England, offered to fund the £70,000 construction of a church on the site (equivalent to £7.5 million in 2016).
Building work, which was undertaken by Rattee and Kett, began in 1885 following the plans of architects Dunn and Hansom, and the foundation stone was laid in June 1887. The construction of such a prominent Catholic church, as well as its dedication to the Forty Martyrs of England and Wales, caused much controversy among local Anglicans and members of the University. Despite this, and the ill health of Mrs Lyne-Stephens, the church was completed and then consecrated on 8 October 1890. The first mass was attended by all the bishops of England and Wales except for Cardinal Manning and Bishop Vaughan.
After its opening, the church saw a great rise in the number of Catholics in the parish. This was partly due to Fr Robert Benson's reputation as a preacher, as well as Mgr Scott's work as parish priest. OLEM also hosted the 1921 Bible Congress, the greatest Catholic gathering in Cambridge since the English Reformation. Between 1922 and 1946, the church was used by the Cambridge Summer School of Catholic Studies.
In a 1941 air raid, a small bomb struck the sacristy, blowing a six-foot hole in the roof and another in the wall of the Sacred Heart chapel. The blast also shattered most of the windows and collapsed part of the organ gallery. The repairs, including replacement windows to the original designs, cost at least £35,000 (equivalent to £1.3 million in 2016).
The building, one of the largest Catholic churches in the United Kingdom, is designed in the Gothic revival style and follows the traditional cruciform layout. It features a polygonal apse and a central lantern tower. The construction includes Casterton stone for the foundation, Ancaster for the plinth, and the remainder in Combe Down. The interior is constructed in Bath stone, Plymouth marble and Newbiggin stone. The spire, the tallest in Cambridge, reaches 214 feet (65 m) and can be seen for a distance of several miles.
To bring the sanctuary in line with the liturgical directives resulting from the Second Vatican Council (1962-1965), its design and re-ordering was done by Gerard Goalen of Harlow. On 7 April 1973, Charles Grant, the Bishop of Northampton, consecrated the present central altar. The original high altar has subsequently been used mainly for reservation of the Blessed Sacrament.