Designing amino-acid sequences that fold into a defined three-dimensional structure, known as protein inverse folding, is central to protein engineering. Current deep-learning approaches effectively encode backbone geometry but cannot readily exploit evolutionary information, particularly for engineered and de novo scaffolds lacking natural sequence homologues. Here, we present FoldMapper, an inverse folding model that recovers evolutionary information directly from protein structure. FoldMapper retrieves structurally similar proteins and aggregates their amino-acid identities into a residue-level structural profile. A graph neural network integrates this profile with backbone geometry to generate sequences compatible with the target structure. On de novo backbones generated by RFdiffusion, FoldMapper-designed sequences fold back to their intended monomer structures in 91–95% of cases, compared with 59% for the strongest baseline. For designed protein binders, FoldMapper achieves up to 78% success, whereas all baselines remain below 40%. On natural proteins, FoldMapper achieves 64.9% sequence recovery while generating 3.7-fold more diverse sequences. These results demonstrate that protein structure contains recoverable evolutionary information and establish FoldMapper as a framework for reliable sequence design of de novo scaffolds and target-binding proteins.