Atlantic cod (Gadus morhua) vertebrae from archaeological sites were used to study the history of the Icelandic Atlantic cod population in the time period of 1500-1990. Specifically, we examine the genetic structure at the Cytochrome b (cytb) and Pantophysin I (PanI) loci, using coalescence modelling to estimate population size and fluctuations. The models are consistent with an expanding population during the warm medieval period with medieval effective population size (N_E) magnitudes larger than observed in current times, a marked bottleneck event at 1400-1500 with continuing decrease in N_E in early modern times. The model results are corroborated by reduction of haplotype and nucleotide variation over time and pair-wise population distance, which partitions a significant portion of nucleotide variation across the 1500 time mark. The mean age of the historical fished stock is high in medieval times with a truncation in age in early modern times.  The population size crash coincides with a period of known cooling in the North Atlantic and we conclude that the collapse may be related to climate or climate induced ecosystem change with subsequent effects of fishing.