Campylobacter jejuni continues to be the leading cause of bacterial food-borne illness worldwide, so improvements to current methods used for bacterial detection and disease prevention are needed. We describe here the genome and proteome of C. jejuni bacteriophage NCTC 12673 and the exploitation of its receptor-binding protein for specific bacterial detection. Remarkably, the 135-kb Myoviridae genome of NCTC 12673 differs greatly from any other proteobacterial phage genome described (including C. jejuni phages CP220 and CPt10) and instead shows closest homology to the cyanobacterial T4-related myophages. The phage genome contains 172 putative open reading frames, including 12 homing endonucleases, no visible means of packaging, and a putative trans-splicing intein. The phage DNA appears to be strongly associated with a protein that interfered with PCR amplification and estimation of the phage genome mass by pulsed-field gel electrophoresis. Identification and analyses of the receptor-binding protein (Gp48) revealed features common to the Salmonella enterica P22 phage tailspike protein, including the ability to specifically recognize a host organism. Bacteriophage receptor-binding proteins may offer promising alternatives for use in pathogen detection platforms.