Marine nitrogen-fixing microorganisms are an important source of fixed nitrogen in oceanic ecosystems. The colonial cyanobacterium Trichodesmium and diatom symbionts were thought to be the primary contributors to oceanic N2 fixation until the discovery of the unusual uncultivated symbiotic cyanobacterium UCYN-A (Candidatus Atelocyanobacterium thalassa). UCYN-A has atypical metabolic characteristics lacking the oxygen-evolving photosystem II, the tricarboxylic acid cycle, the carbon-fixation enzyme RuBisCo and de novo biosynthetic pathways for a number of amino acids and nucleotides. Therefore, it is obligately symbiotic with its single-celled haptophyte algal host. UCYN-A receives fixed carbon from its host and returns fixed nitrogen, but further insights into this symbiosis are precluded by both UCYN-A and its host being uncultured. In order to investigate how this syntrophy is coordinated, we reconstructed bottom-up genome-scale metabolic models of UCYN-A and its algal partner to explore possible trophic scenarios, focusing on nitrogen fixation and biomass synthesis. Since both partners are uncultivated and only the genome sequence of UCYN-A is available, we used the phylogenetically related Chrysochromulina tobin as a proxy for the host. Through the use of flux balance analysis (FBA), we determined the minimal set of metabolites and biochemical functions that must be shared between the two organisms to ensure viability and growth. We quantitatively investigated the metabolic characteristics that facilitate daytime N2 fixation in UCYN-A and possible oxygen-scavenging mechanisms needed to create an anaerobic environment to allow nitrogenase to function. This is the first application of an FBA framework to examine the tight metabolic coupling between uncultivated microbes in marine symbiotic communities and provides a roadmap for future efforts focusing on such specialized systems.