The epidemic pathogen Vibrio cholerae senses and responds to different external stresses it encounters in the aquatic environment and in the human host. One stress that V. cholerae encounters in the host is exposure to antimicrobial peptides on mucosal surfaces. We used massively parallel cDNA sequencing (RNA-Seq) to quantitatively identify the transcriptome of V. cholerae grown in the presence and absence of sub-lethal concentrations of the antimicrobial peptide polymyxin B. We evaluated the transcriptome of both wild type V. cholerae and a mutant carrying a deletion of vc1639, a putative sensor kinase of an uncharacterized two-component system, under these conditions. In addition to many previously uncharacterized pathways responding with elevated transcript levels to polymyxin B exposure, we confirmed the predicted elevated transcript levels of a previously described LPS modification system in response to polymyxin B exposure. Additionally, we identified the V. cholerae homologue of visP (ygiW) as a regulatory target of VC1639. VisP is a conserved periplasmic protein implicated in lipid A modification in Salmonellae. This study provides the first systematic analysis of the transcriptional response of Vibrio cholerae to polymyxin B, raising important questions for further study regarding mechanisms used by V. cholerae to sense and respond to envelope stress.