“Rude” o “Rood” és una antiga paraula anglesa que significa la Creu de la Crucifixió.

La primera església en aquest mateix lloc, va ser fundada pel rei David I l’any 1129, però va ser destruïda en un incendi l’any 1406. Després, el Lord Chamberlain d’Escòcia va fer un donatiu per a la construcció d’una nova església i, aproximadament l’any 1414 la nau, l’ala sud i la torre van quedar finalitzades. Aquesta part de l’església amb les seves columnes escoceses circulars, els seus arcs gòtics i el sostre original de roure, actualment es mostra, tot i els canvis realitzats, gairebé com va ser edificada.

L’església no era suficientment gran per a tota la congregació i es va ampliar amb el cor ubicat a la part oriental, que va ser construït entre els anys 1507 i 1546 per artesans locals sota la inspirada direcció del mestre d’obres John Coutts.

A l’any 1656, després d’una disputa entre els dos pastors de l’església i els seus partidaris, l’Ajuntament va ordenar la construcció d’un envà on ara es troba la travessia, i es formaren per tant dues esglésies, l’església de l’oest i l’església de l’est, cada una d’elles amb el seu propi pastor. Aquesta situació va continuar fins el 1935 quan les dues congregacions es van unir amb un sol pastor al capdavant.

La restauració més important es va realitzar entre els anys 1936 i 1940. L’envà va ser enderrocat, els creuers van ser ampliats, es va construir l’aresta de la volta sobre la travessia, es van aixecar els terres del cor i del presbiteri i es van ubicar sota el sol del cor les sagristies i la Sala Capitular.

Entre l’any 1965 i l’any 1968 es van realitzar més obres: La renovació del traçat de la pedra d’algunes finestres, la reposició i replè de tota la mamposteria i la renovació del sistema de calefacció.

En l’any 1970 es va refondre el conjunt de les 6 campanes de la torre que es van tornar a penjar. Actualment es poden fer sonar manualment o mecànicament.

Entre 1987 i 1993 es va fer una restauració de l’església amb un cost de 1.250.000 £.

Maria, Reina d’Escòcia, va resar en aquesta església i John Knox hi va predicar. El 29 de juliol de l’any 1567, el fill de Maria, l’Infant, va ser coronat en aquesta església com a Rei Jaume VI d’Escòcia, més tard, a la mort de la reina Isabel en 1603, passà a Jaume I del Regne Unit. Per tant, aquesta església, actualment utilitzada encara com a parròquia, és la única en tota Escòcia en la qual va tenir lloc una coronació.