There has been a place of worship on the current site since around the twelfth century. The earliest known records of the church state that the first church here was called St Peter-without-Trumpington Gate, to distinguish it from St Peter by the Castle. It was controlled by three successive generations of the same family until 1207. After that date it was given to the Hospital of St John the Evangelist and served by chaplains from that foundation. In the early 1280s, Hugh de Balsham, Bishop of Ely, lodged some scholars in the Hospital but to his dismay found soon that the sick and the students could not live in harmony together. The students were moved in 1284 to the site of what is now Peterhouse; this was the origin of the first Cambridge college. By the 1340s the church was in such a bad state that the fellows of Peterhouse decided to rebuild it. In 1352, the new building had the dual purpose of College Chapel and Parish Church. At this time, it was rededicated to the Blessed Virgin Mary. In 1632 Peterhouse built a separate Chapel and St Mary the Less reverted to being a Parish Church. Richard Crashaw, the metaphysical poet, was a priest there from 1638 to 1643, at the same time that he was a Fellow of Peterhouse. In 1643, after his departure, many of the Church's ornaments and statues were damaged or destroyed by the Puritan iconoclast William Dowsing. The damage to the sedilia and the entrance to the Lady Chapel has never been repaired. In 1741 the church was refitted with wooden panelling, box pews, choir gallery, and the present pulpit. From 1856–7 Sir George Gilbert Scott restored the church and removed the 18th-century panelling. Further restoration work was carried out in 1876 and 1891, but by 1880 the church was much as it is now. The south, or Lady Chapel, was added in 1931 and designed by T. H. Lyon, the architect of Sidney Sussex College Chapel. The Parish Centre at the west end of the church was built in 1892 and enlarged in 1990 and again in 2011. Reverend Godfrey Washington, who died on 28 September 1729, is buried in Little St Mary's. His memorial is on the north wall close to the main door. The coat of arms of the Washington family, a black eagle atop a shield of red stars and stripes, adorns the tablet. It is from this coat of arms that the 'Stars and Stripes' of the U.S. National Flag, and the U.S. black eagle emblem, may derive.
