Multiple antimicrobial-resistant strains of Salmonella enterica serovar Newport have been recorded. Study on phages infecting S. Newport may provide new therapeutics or diagnostics for this pathogen. Here, we describe the complete genome sequence of the T4-like phage Melville that uses S. Newport as one of its hosts.