The population of Newfoundland and Labrador (NL) is largely derived from settlers who migrated primarily from England and Ireland in the 1700s-1800s. Previously described as an isolated founder population, based on historical and demographic studies, data on the genetic ancestry of this population remains fragmentary. Here we describe the largest investigation of patrilineal ancestry in NL. To determine the paternal genetic structure of the population, 1,110 Y chromosomes from an NL-based cohort were analyzed using 5,761 Y-specific SNPs. We identified 160 distinct terminal haplogroups, the majority of which (71.4%) belong to the R1b haplogroup. When compared with global reference populations, the NL population haplogroup composition and frequencies primarily resemble those observed in English and Irish ancestral source populations. There is also evidence of genetic contributions from Basque, French, Portuguese, and Spanish fishermen and early settlers who frequented NL. Interestingly, the observed population structure shows geographical and religious clustering that can be associated with the settlement of the ancestral source populations from predominantly Protestant, England, and Catholic, Ireland respectively. For example, the R1b-M222 haplogroup, seen in people of Irish descent, is found clustered in the Irish-settled Southeast region of NL. The clustering and expansion of Y haplogroups in conjunction with the geographical and religious clusters illustrate that limited subsequent in-migration, geographic isolation, and societal factors have contributed to the genetic substructure of the NL population and its designation as a founder population.