As different chemicals, methyl parathion (MP) and cadmium (Cd) can induce neurotoxicity on the brain of aquatic ecosystems. This study aims to explore the differential expression proteins in the brain induced by their joint stress and their joint effects, which are poorly reported, and devotes finding novel biomarkers for monitoring their contamination in water and assessing their neurological effects. The bioaccumulation of MP and Cd in tissues after 96 h of exposure was first analyzed by GC and inductively coupled plasma-MS to provide insights into the interaction. Protein profile changes in the brains of the zebrafish (Danio rerio) exposed to MP and Cd were further investigated using the proteomic approach. The correlation of gene expression on the transcription level of mRNA and the translation level of protein was examined by real-time quantitative PCR and Western blotting analysis. It showed that Cd and MP have an interaction on their bioaccumulation, which suggests that their joint effect over 96 h might be antagonistic. Proteomics revealed that 22 protein spots changed their expression levels under stress, of which 16 proteins were identified using MS. These proteins were involved in oxidation/reduction, metabolism, energy production, receptor activity, and cytoskeleton assembly. Among them, five proteins with a remarkable abundance change are significantly suggested to play important roles in the joint effect. This work demonstrates that there exists an interaction between MP and Cd toxicities, which may aid in our understanding of the mechanism of neurotoxicity induced by joint stress. The results may also provide the possibility of the establishment of candidate biomarkers for monitoring MP and Cd contamination in water.