A metabolism is a complex chemical reaction system, whose metabolic genotype – the DNA encoding the enzymes catalyzing these reactions – can be compactly represented by its complement of metabolic reactions. Here, we analyze a space of such metabolic genotypes. Specifically, we study nitrogen metabolism and focus on nitrogen utilization phenotypes that are defined through the viability of a metabolism – its ability to synthesize all essential small biomass precursors – on a given combination of sole nitrogen sources. We randomly sample metabolisms with known phenotypes from metabolic genotype space with the aid of a method based on Markov Chain Monte Carlo sampling. We find that metabolisms viable on a given nitrogen source or a combination of nitrogen sources can differ in as much as 80 percent of their reactions, but can form networks of genotypes that are connected to one another through sequences of single reaction changes. The reactions that cannot vary in any one metabolism differ among metabolisms, and include a small core of “absolutely superessential” reactions that are required in all metabolisms we study. Only a small number of reaction changes are needed to reach the genotype network of one metabolic phenotype from the genotype network of another metabolic phenotype. Our observations indicate deep similarities between the genotype spaces of macromolecules, regulatory circuits, and metabolism that can facilitate the origin of novel phenotypes in evolution.