The effect of high concentrations of arsenic has been investigated in Caenibacter arsenoxydans, a β-proteobacterium isolated from an arsenic contaminated environment and able to oxidize arsenite to arsenate. As the genome of this bacterium has not yet been sequenced, the use of a specific proteomic approach based on nano-high performance liquid chromatography tandem mass spectrometry (nanoLC-MS/MS) studies and de novo sequencing to perform cross-species protein identifications was necessary. In addition, a random mutational analysis was performed. Twenty-two proteins and 16 genes were shown to be differentially accumulated and expressed, respectively, in cells grown in the presence of arsenite. Two genes involved in arsenite oxidation and one in arsenite efflux as well as two proteins responsible for arsenate reduction were identified. Moreover, numerous genes and proteins belonging to various functional classes including information and regulation pathways, intermediary metabolism, cell envelope and cellular processes were also up- or down-regulated, which demonstrates that bacterial response to arsenic is pleiotropic.