Like many bacteria, Vibrio cholerae deploys a harpoon-like type VI secretion system (T6SS) to compete against other microbes in environmental and host settings. The T6SS punctures adjacent cells and delivers toxic effector proteins that are harmless to bacteria carrying cognate immunity factors. Only four effector/immunity pairs encoded on one large and three auxiliary gene clusters have been characterized from largely clonal, patient-derived strains of V. cholerae. We sequence two dozen V. cholerae strain genomes from diverse sources and develop a novel and adaptable bioinformatics tool based on hidden Markov models. We identify two new T6SS auxiliary gene clusters and describe Aux 5 here. Four Aux 5 loci are present in the host strain, each with an atypical effector/immunity gene organization. Structural prediction of the putative effector indicates it is a lipase, which we name TleV1 (type VI lipase effector Vibrio). Ectopic TleV1 expression induces toxicity in Escherichia coli, which is rescued by co-expression of the TliV1a immunity factor. A clinical V. cholerae reference strain expressing the Aux 5 cluster uses TleV1 to lyse its parental strain upon contact via its T6SS but is unable to kill parental cells expressing the TliV1a immunity factor. We develop a novel bioinformatics method and identify new T6SS gene clusters in V. cholerae. We also show the TleV1 toxin is delivered in a T6SS manner by V. cholerae and can lyse other bacterial cells. Our web-based tool can be modified to identify additional novel T6SS genomic loci in diverse bacterial species.