The vast majority of bacterial diversity lies within phylum-level lineages called "candidate phyla," which lack isolated representatives and are poorly understood. These bacteria are surprisingly abundant in the oral cavity of marine mammals. We employed a genome-resolved metagenomic approach to recover and characterize genomes and functional potential from microbes in the oral gingival sulcus of two bottlenose dolphins (Tursiops truncatus). We detected organisms from 24 known bacterial phyla and one archaeal phylum. We also recovered genomes from two deep-branching, previously uncharacterized phylum-level lineages (here named "Candidatus Delphibacteria" and "Candidatus Fertabacteria"). The Delphibacteria lineage is found in both managed and wild dolphins; its metabolic profile suggests a capacity for denitrification and a possible role in dolphin health. We uncovered a rich diversity of predicted Cas9 proteins, including the two longest predicted Cas9 proteins to date. Notably, we identified the first type II CRISPR-Cas systems encoded by members of the Candidate Phyla Radiation. Using their spacer sequences, we subsequently identified and assembled a complete Saccharibacteria phage genome. These findings underscore the immense microbial diversity and functional potential that await discovery in previously unexplored environments.