Plants have evolved a series of tolerance mechanisms to saline stress, which perturbs physiological processes throughout the plant. To identify genetic mechanisms associated with salinity tolerance, we performed linkage analysis and genome-wide association study (GWAS) on maintenance of root growth of Arabidopsis thaliana in hydroponic culture with weak and severe NaCl toxicity. The top 200 single-nucleotide polymorphisms (SNPs) determined by GWAS could cumulatively explain approximately 70% of the variation observed at each stress level. The most significant SNPs were linked to the genes of ATP-binding cassette B10 and vacuolar proton ATPase A2. Several known salinity tolerance genes such as potassium channel KAT1 and calcium sensor SOS3 were also linked to SNPs in the top 200. In parallel, we constructed a gene co-expression network to independently verify that particular groups of genes work together to a common purpose. We identify molecular mechanisms to confer salt tolerance from both predictable and novel physiological sources and validate the utility of combined genetic and network analysis. Additionally, our study indicates that the genetic architecture of salt tolerance is responsive to the severity of stress. These gene datasets are a significant information resource for a following exploration of gene function. © 2016 John Wiley & Sons Ltd.