From 1839 until 1917 the catholic parish of Harmelen had used a neo-Classical church, a relatively large building that could accomodate 650 people. However, it was badly built and expensive to maintain. In 1914 it was decided to replace it. Part of the old church was demolished while the remaining part was later given a new use as a chapel.

The new church was designed in 1916 by Jan Stuyt. It's in his recognisable neo-Romanesque style and bears similarities to many of his other churches: the Italian style tower, the side-aisles with pointed gables and the decorative tile mozaics. Although the bishop of Utrecht hesitated to accept the design and urged for a cheaper option without a tower, such financial matters eventually were of less importance than the pride of the parish, and the church was built with the tower. However, not the entire plan was fullfilled. The World War had caused financial problems and difficulties with the delivery of natural stone, and some simplifications were needed, especially in the interior.

The St. Bavo is a three-aisled pseudo-basilica, with high side-aisles with pointed gables that allow larger windows. The choir has a lower, semi-circular apse which is flanked by an octagonal stair-turret on the right side. On the eastern side the nave is flanked on both sides by sacristies.