Rehabilitation of coastal vegetation is reliant on the successful establishment of halophytic seedlings. Seed germination variation among populations of two desert halophytes, Arthrocnemum macrostachyum and Suaeda vermiculata, was assessed under seven salinity levels from 0 to 1,000 mM NaCl. recovery of germination in seeds previously exposed to salinity stress was also assessed. Correlation between seed fresh weight and germination was strongly positive in S. vermiculata (r = 0.852; P = 0.007), and moderate in A. macrostachyum (r = 0.547; P = 0.066). Seed germination of A. macrostachyum increased in similar proportion to a decline in the mean germination time (MGT) in a weak but significant correlation (r = 0.492; P = 2.4 × 10−3). Similarly, the decline of MGT was associated with a decline of germination synchrony (SYN; r = 0.551; P = 9.7 × 10−4). Increased germination of S. vermiculata seeds was not associated with any change in MGT (P value = 0.078), but showed a significant increase in SYN (r = 0.851; P = 1.1 × 10−5). A similar pattern was found between SYN and MGT which shows a strong positive correlation (r = 0.687; P = 6.7 × 10−4). Seed germination of S. vermiculata appears to be strongly influenced by provenance, but the relationship in A. macrostachyum is less clear. The lower soil pH also promoted the seed germination with consequent a decrease of mean germination time (MGT). Efficiency of coastal restoration projects can be improved by selecting natural seed sources from locations and/or seasons producing above-average seed weight.