The Romanesque church consisted of a west tower, aisleless nave and chancel, built with large squared stones. From the 12thc. church survive the W tower arch, the S nave doorway and part of the N nave doorway. The E end was extended, probably in the 13thc. Other changes seem also to have been made in the late-15th/early 16thc. A 16thc. font was discovered in the late 18thc. (now in the Roman Catholic church in Broxburn) and a surviving late medieval bell was made in 1503. Otherwise the church remained the same until after the Reformation. The Shairp Aisle, on the S side, was added c.1620 and in 1644 the Buchan Gallery (only stairs for this survive) was also built. During the 18thc., a further addition was made to the N side, called the Middleton Aisle. Later, in 1878, the majority of the N Romanesque wall was removed to build a much larger addition to that side of the church. By 1896, the shafts of the S doorway had also been renewed. Finally, in 1937-40 a complete restoration of the church was undertaken, during which time the arch from the nave into the tower was opened up.

Strathbrock (the former name for the settlement at Uphall) was given to Freskin/Freskyn by King David I, but the exact date is unknown. Freskin took part in quelling the c.1130 insurrection in Moray and was rewarded with the area of Duffus (Moray), where he/his family built a motte and bailey castle. It appears that he was already in control of Strathbrock by this time and may have built a castle there. There is no reference to the 12thc. church, but the east end of the church seems to have been extended in the 13thc. The first known reference to the church comes in the 1270s, when it occurs in the accounts of a papal tax-collector in Scotland as a free parsonage. In 1435/6 the church was annexed to a prebend of the church of St Mary on the Rock at St Andrews, but by 1462 the benefice had fallen vacant and there was a dispute over the patronage of the church, which continued for many years after this. At the Reformation, the annexation to St Mary on the Rock was still in force.

The Freskin connection with Uphall is significant and it seems not unlikely that he was responsible for the church. After Duffus in Moray was given to Freskin, he moved to that area. The simplicity of the church at Uphall, the use of large squared stones in its construction, along with the historic information about Freskin, suggests that the church was probably built after 1124 (when David became king) and 1171 (be which time Freskin had died). A starting date in the second half of the 1120s or in the 1130s seems entirely possible.