Eldste omtale av en kirke på Vardø er i de islandske annaler for 1307, at den da ble innviet av erkebiskop Jørund (Herra Jorundr for norðr a Halogaland i Varseyiar oc vigði þar kirkiu, Storm 1888:74). Kirkegården kan avgrenses ved Søndre Langgate 13-19 i vest, Skolegaten 14-20 i øst: ”Skjeletter fra den gamle kirkegården graves opp hver gang det er byggearbeider i dette kvartalet” (Simonsen 1991:194). Kirkegården har sirkelformet avgrensning. På et kart fra 1692 framstår bygningen som en langkirke med takrytter over skipet i vest. I 1750 noterte Nannestad: ”Kirkegaarden [for nykirken] er ikun maadelig indhegnet med Torv og Steen (…) Et Steenkast derfra er den gamle Kirkegaard, som endnu er indhegnet, hvor den gamle Kirke har staaet”. (Wolff 1942:32f, Trædal 2008:257ff m/ref.).