A novel Vibrio phage, P23, belonging to the family Siphoviridae was isolated from the surface water of the Yellow Sea, China. The complete genome of this phage was determined. A one-step growth curve showed that the latent period was approximately 30 min, the burst size was 24 PFU/cell, and the rise period was 20 min. The phage is host specific and is stable over a range of pH (5–10) and temperatures (4–65 °C). Transmission electron microscopy showed that phage P23 can be categorized into the Siphoviridae family, with an icosahedral head of 60 nm and a long noncontractile tail of 144 nm. The genome consisted of a linear, double-stranded 40.063 kb DNA molecule with 42.5% G+C content and 72 putative open reading frames (ORFs) without tRNA. The predicted ORFs were classified into six functional groups, including DNA replication, regulation and nucleotide metabolism, transcription, phage packaging, phage structure, lysis, and hypothetical proteins. The Vibrio phage P23 genome is a new marine Siphoviridae-family phage genome that provides basic information for further molecular research on interaction mechanisms between bacteriophages and their hosts.