A phage infecting Mycobacterium phlei was isolated in 1958 from a soil sample in Hungary. Some physicochemical and biological properties of the virus were described in independent studies over the years. Here, we report the genome sequence of this early mycobacteriophage isolate. The Phlei phage genome measured 50,418 bp, had a GC content of 60.1 % and was predicted to encode 81 proteins and three tRNAs. Phylogeny of the tape measure protein revealed genetic relatedness to other early isolates of mycobacteriophages within subcluster A2. The genomic organization and genetic relationships to other strains showed that the Phlei phage belongs to a novel genetic cluster, designated A13.