The founder population of Newfoundland and Labrador (NL) is a unique genetic resource, in part due to its geographic and cultural isolation, where historical records describe a migration of European settlers, primarily from Ireland and England, to NL in the 18th and 19th centuries. Whilst its historical isolation, and increased prevalence of certain monogenic disorders are well appreciated, details of the fine-scale genetic structure and ancestry of the population are lacking. Understanding the genetic origins and background of functional, disease causing, genetic variants would aid genetic mapping efforts in the Province. Here, we leverage dense genome-wide SNP data on 1,807 NL individuals to reveal fine-scale genetic structure in NL that is clustered around coastal communities and correlated with Christian denomination. We show that the majority of NL European ancestry can be traced back to the south-east and south-west of Ireland and England, respectively. We date a substantial population size bottleneck approximately 10-15 generations ago in NL, associated with increased haplotype sharing and autozygosity. Our results reveal insights into the population history of NL and demonstrate evidence of a population conducive to further genetic studies and biomarker discovery.