The earliest parts of the church consist of an unaisled nave and W tower, which includes a spiral stair in the SE corner. There was likely also an eastern chancel, but this no longer exists. Early doorways survive in the S nave wall (now blocked) and E wall (moved from the N side of the church). Large sections of the church walls are medieval, but there have been several additions and other interventions over the centuries. A projecting burial wing on the SE corner of the nave, called the ‘Stair Aisle’ was built in the 17thc, as well as the upper part of the W tower and belfry above its eastern wall. The interior was re-designed in the 19thc. However, a gothic arch (now blocked) can be seen on the N side of the E end of the nave, and there is another arch from the Transitional period in the E wall of the W tower. Drawings show that a post-Reformation exterior staircase was built onto the S side of the W end of the nave, with a doorway inserted into the gallery level. This has subsequently been taken down, the doorway removed and a Romanesque-style doorway built at ground-floor level. In 1822 an aisle was added to the N side of the nave and the old N doorway rebuilt in the gable of this aisle. But in 1884 the aisle was extended and the doorway moved to the E wall of the church, where it became the principle entrance to the church.

The first reference to ‘Liston’ appears c.1163. Then, c.1298, an English chronicler refers to ‘Temple Liston’, almost certainly referring to the Knights Templar who owned some of the present parish. Although it has been said at times that the church building might be associated with them, there is no known evidence to support this. Only from the 14thc does one hear of ‘Kirkliston’. On 11 September 1244, the church of Liston was dedicated by David de Bernham, Bishop of St Andrews, but to which saint the church was dedicated is not recorded. In 1450, James Kennedy, Bishop of St Andrews, petitioned the Pope for the appropriation of the church. This was granted in June 1451. John Gray was the last rector recorded, but he disappears from the records after September 1451. Following this, Kirkliston became a ‘mensal benefice’. In 1387, however, the church was already supposed to be annexed to the bishop of St Andrews, but it seems not to have been effected at that time. In the late medieval period, the bishop of St Andrews was understood to be the parson, and therefore entitled to receive the tithes from the parish. An episcopal manor was also established there. The church lands were leased to John Douglas in 1528. Finally, in 1593 an act dissolving the parsonage and vicarage was passed.

The earliest sections of Kirkliston church, including the doorways, west tower, corbels, stringcourse and sections of the walls of the nave, are generally said to be late-12thc or c.1200. However, the doorway now in the E wall has capitals that do not all appear to come from the same original location and may possibly be of different dates, the earliest, including the waterleaf/broadleaf capitals, having been carved in the latter part of the 12thc. Also, the stonework of the W tower archway, now partially blocked by the modern interior staircase, does not course with the tower wall next to it, nor does the exterior stonework of the tower and nave. Inside the church is preserved an old model of the church as it existed between 1859 and 1884. The doorway now in the E wall is shown on the N wall of the N extension. The doorway on the model is not shown with a gabled area above this, but rather as a simple vertical. Earlier drawings of the blocked S doorway suggest there may have been more above the doorway and that this was simplified at a more recent date. The original outer W shaft and base of this doorway were probably destroyed when the exterior staircase was built, which overlapped the westernmost part of the doorway. The early drawings of this doorway also show that the main shaft of the outer E side was also missing at that time. Various decorative features suggest comparison with work on the cathedral of St Andrews (begun 1161), both in-situ and ex-situ.