This study is the first to investigate the microbial ecology of the Tutum Bay (Papua New Guinea) shallow-sea hydrothermal system. The subsurface environment was sampled by SCUBA using push cores, which allowed collection of sediments and pore fluids. Geochemical analysis of sediments and fluids along a transect emanating from a discrete venting environment, about 10 mbsl, revealed a complex fluid flow regime and mixing of hydrothermal fluid with seawater within the sediments, providing a continuously fluctuating redox gradient. Vent fluids are highly elevated in arsenic, up to ∼1 ppm, serving as a “point source” of arsenic to this marine environment. 16S rRNA gene and FISH (fluorescence in situ hybridization) analyses revealed distinct prokaryotic communities in different sediment horizons, numerically dominated by Bacteria. 16S rRNA gene diversity at the genus level is greater among the Bacteria than the Archaea. The majority of taxa were similar to uncultured Crenarchaea, Chloroflexus, and various heterotrophic Bacteria. The archaeal community did not appear to increase significantly in number or diversity with depth in these sediments. Further, the majority of sequences identifying with thermophilic bacteria were found in the shallower section of the sediment core. No 16S rRNA genes of marine Crenarchaeota or Euryarchaeota were identified, and none of the identified Crenarchaeota have been cultured. Both sediment horizons also hosted “Korarchaeota”, which represent 2–5% of the 16S rRNA gene clone libraries. Metabolic functions, especially among the Archaea, were difficult to constrain given the distant relationships of most of the community members from cultured representatives. Identification of phenotypes and key ecological processes will depend on future culturing, identification of arsenic cycling genes, and RNA-based analyses.