Understanding the origin and evolution of genes is crucial to explaining the origin and evolution of novel phenotypes and ultimately the diversity of life. Although it was previously thought that almost all new genes were derived from duplication-related processes, recent work has revealed that de novo genes, which are genes born from ancestrally non-genic sequences, also contribute to gene and functional innovation. However, the earliest steps in the birth process of de novo genes and how they are maintained in populations and species were largely unknown. We combined base-level whole-genome alignments, computational structure modeling, and functional approaches to study the origination, evolution, and protein structure of lineage-specific de novo genes. We observed a gradual shift in sequence composition, evolutionary rates, and expression patterns based on gene ages. Intriguingly, there were minimal protein structural changes in young and old de novo genes. Ancestral sequence reconstruction revealed that well-folded proteins are often born folded, and many are enriched with transmembrane and signal proteins. Single-cell RNA sequencing data show that these genes are enriched in germ cells, supporting a function and selective force related to reproduction. We also used a deep learning approach to investigate the basis of new gene regulation. Our study provides a systematic overview of the origin, evolution, and structural changes of de novo genes.