Protein scientists are paving the way to a new phase in protein design and engineering. Approaches and methods are being developed that could allow the design of proteins beyond the confines of natural protein structures. This possibility of designing entirely new proteins opens new questions: What do we build? How do we build into protein-structure space where there are few, if any, natural structures to guide us? To what uses can the resulting proteins be put? And, what, if anything, does this pursuit tell us about how natural proteins fold, function and evolve? We describe the origins of this emerging area of fully de novo protein design, how it could be developed, where it might lead, and what challenges lie ahead.