Naturally evolved saline tolerant rice landraces found along the coastline of India are a valuable genomic resource to explore the complex, polygenic nature of salinity tolerance. In the present study, a set of 28 genome wide SSR markers, 11 salt responsive genic SSR markers and 8 Saltol QTL linked SSR markers were used to estimate genetic relatedness and population structure within a collection of 47 rice landraces (including a tolerant and 2 sensitive checks) originating from geographically divergent coastal regions of India. All three marker types identified substantial genetic variation among the landraces, as evident from their higher PIC values (0.53 for genomic SSRs, 0.43 for Genic SSRs and 0.59 for Saltol SSRs). The markers RM431, RM484 (Genomic SSRs), OsCAX (D), OsCAX (T) (Genic SSRs) and RM562 (Saltol SSR) were identified as good candidates to be used in breeding programs for improving salinity tolerance in rice. STRUCTURE analysis divided the landraces into five distinct populations, with classification correlating with their geographical locations. Principal coordinate and hierarchical cluster analyses (UPGMA and neighbor joining) are in close agreement with STRUCTURE results. AMOVA analysis indicated a higher magnitude of genetic differentiation within individuals of groups (58%), than among groups (42%). We also report the development and validation of a new Cleavage Amplified Polymorphic Sequence (CAPS) marker (OsHKT1;5V395) that targets a codon in the sodium transporter gene OsHKT1;5 (Saltol/SKC1 locus) that is associated with sodium transport rates in the above rice landraces. The CAPS marker was found to be present in all landraces except in IR29, Kamini, Gheus, Matla 1 and Matla 2. Significant molecular genetic diversity established among the analyzed salt tolerant rice landraces will aid in future association mapping; the CAPS marker, OsHKT1;5V395 can be used to map rice landraces for the presence of the SNP (Single Nucleotide Polymorphism) associated with increased sodium transport rates and concomitant salinity tolerance in rice.