We describe a novel filamentous phage, designated VGJ phi, isolated from strain SG25-1 of Vibrio cholerae O139, which infects all O1 (classical and El Tor) and O139 strains tested. The sequence of the 7,542 nucleotides of the phage genome reveals that VGJ phi has a distinctive region of 775 nucleotides and a conserved region with an overall genomic organization similar to that of previously characterized filamentous phages, such as CTX phi of V. cholerae and Ff phages of Escherichia coli. The conserved region carries 10 open reading frames (ORFs) coding for products homologous to previously reported peptides of other filamentous phages, and the distinctive region carries one ORF whose product is not homologous to any known peptide. VGJ phi, like other filamentous phages, uses a type IV pilus to infect V. cholerae; in this case, the pilus is the mannose-sensitive hemagglutinin. VGJ phi-infected V. cholerae overexpresses the product of one ORF of the phage (ORF112), which is similar to single-stranded DNA binding proteins of other filamentous phages. Once inside a cell, VGJ phi is able to integrate its genome into the same chromosomal attB site as CTX phi, entering into a lysogenic state. Additionally, we found an attP structure in VGJ phi, which is also conserved in several lysogenic filamentous phages from different bacterial hosts. Finally, since different filamentous phages seem to integrate into the bacterial dif locus by a general mechanism, we propose a model in which repeated integration events with different phages might have contributed to the evolution of the CTX chromosomal region in V. cholerae El Tor.