New materials can solve many (though not all) of the world’s problems though faster, smaller-scale and cheaper processing and storage of information and energy. Improving and optimizing the materials we already use for these purposes can only take us so far – what about something really new? How would we know where to look? Information about the structures and properties of experimentally known materials, as organized into a crystallographic database, provides the initial data for a rough map of the space of possible materials. Using the theory of quantum mechanics to perform first-principles computer simulations of the properties of known and as-yet hypothetical materials from first principles, using only their chemical composition as input, we can augment the database with the results of computer experiments to develop the map. Drawing on the unique capability of first-principles calculations to identify low-energy metastable states in addition to the equilibrium phase, we can predict phase transitions and functional properties “de novo”: that is, without prior experimental clues. Several examples of such predictions for functional perovskite oxide materials will be presented. The challenges and promise of theoretical materials design and theoretical-experimental integration will be discussed.