Sequence alignment is a standard method to infer evolutionary, structural, and functional relationships among proteins. The quality of alignments depends on the substitution matrix used. We derive matrices based on superimpositions from protein pairs of similar structure, but of low or no sequence similarity. In a performance test the matrices are compared to 12 other previously published matrices. It is found that the structure derived matrices are applicable for comparisons of distantly related sequences. We investigate the influence of evolutionary relationships of protein pairs on the alignment accuracy.