Amino-acid substitution models are essential in most methods to infer phylogenies from protein data. These models represent the ways in which proteins evolve and substitutions accumulate along the course of time. It is widely accepted that the substitution processes vary depending on the structural configuration of the protein residues. However, this information is not (or is rarely) used in phylogenetic studies, though the three-dimensional structure of dozens of thousands of proteins has been elucidated. Here we reinvestigate the question in order to fill this gap. We use an improved estimation methodology and a very large database comprising 1,471 non-redundant globular protein alignments with structural annotations to estimate new amino-acid substitution models accounting for the secondary structure and solvent accessibility of the residues. These models incorporate a confidence coefficient which is estimated from the data and reflects the reliability of structural annotations in the analyzed sequences. Our results with 300 independent test alignments show an impressive likelihood gain, compared to standard models such as JTT or WAG. Moreover, the use of these models induces significant topological changes in the inferred trees, which should be of primary interest to phylogeneticists. Our data, models and software are available for download from http://atgc.lirmm.fr/phyml-structure/.