Protein structure exhibits greater evolutionary preservation than sequence, due to its closer relationship to function and therefore to phenotype. The use of protein structure to probe evolutionary relationships has been attempted previously1,2 and shown to be promising. Protein structures have also been categorised according to both structural and sequence similarity in databases such as SCOP. Here we investigate the capacity of standard measures of protein structural similarity to cope with proteins of different sequence and length, and elucidate the limits of their usefulness. We define the sequence overlap length at which otherwise identical protein structures are no longer deemed similar, and the degree of structural similarity at which these metrics can no longer distinguish two protein structures. Ultimately, evolutionary relationships derived from comparing protein structure using these tools have the potential to reorganise protein structural databases, changing the way we use and interpret these resources as well as our understanding of how molecular-level changes drive evolution.