Statistically significant multiple sequence alignment construction is an important task that has many biological applications. We applied the method for multiple alignments of highly divergent sequences (MAHDS) to construct multiple sequence alignments (MSAs) for 490 protein families with less than 20% identity between family members. The method uses random symmetric position–weight matrices (PWMs) and a genetic algorithm to construct a multiple alignment. PWM symmetry is essential because it makes PWMs comparable and recoverable at all steps of the MAHDS algorithm, which reduces the optimal MSA search task to a PWM optimization task. A Monte Carlo method is applied to assess the statistical significance of the resulting alignments. The statistical significance of the constructed MSAs was compared with that of MSAs obtained using T-Coffee and MUSCLE algorithms. The results showed that for 476 of the 490 families, the MAHDS method created much more statistically significant MSAs than T-Coffee and MUSCLE, whereas for 138 families, only MAHDS could construct statistically significant MSAs. These findings indicate that MAHDS calculate statistically significant alignments in cases when the other methods create purely random MSAs and are, therefore, the most appropriate method to construct MSAs for families of proteins with weak sequence similarities for amino acid annotation.