We identified a 4.7kb cryptic plasmid in all ctxAB+ Vibrio cholerae strains we tested. An isolate of the V. cholerae classical biotype strain 0395 that harbours the cryptic plasmid at high copy number was found. Hybridization analysis demonstrated that sequences highly related or identical to this plasmid exist in all toxigenic strains of V. cholerae but were notably absent in all non-toxigenic environmental isolates that lacked the genes for toxin-co-regulated pili and the filamentous CTX prophage. Accordingly, we have named the cryptic plasmid pTLC for toxin-linked cryptic. The complete nucleotide sequence of pTLC from the high-copy-number isolate was determined. The largest open reading frame in the plasmid is predicted to encode a protein similar to the replication initiation protein (pII) of Escherichia coli F-specific filamentous phages. The nucleotide sequence of pTLC also facilitated the structural characterization of the DNA homologous to pTLC in other strains of V. cholerae. pTLC-related DNA exists in these strains as both low-copy-number, covalently closed circular DNA and tandemly duplicated, chromosomally integrated DNA. Remarkably, the chromosomally integrated form of pTLC is adjacent to the CTX prophage. The strain distribution, chromosomal location and DNA sequence of pTLC suggests that it may be a genetic element that plays some role in the biology of CTXphi, perhaps facilitating either its acquisition or its replication.