Five malathion-degrading bacterial strains were enriched and isolated from soil samples collected from different agricultural sites in Cairo, Egypt. Malathion was used as a sole source of carbon (50 mg/l) to enumerate malathion degraders, which were designated as IS1, IS2, IS3, IS4, and IS5. They were identified, based on their morphological and biochemical characteristics, as Pseudomonas sp., Pseudomonas putida, Micrococcus lylae, Pseudomonas aureofaciens, and Acetobacter liquefaciens, respectively. IS1 and IS2, which showed the highest degrading activity, were selected for further identification by partial sequence analysis of their 16S rRNA genes. The 16S rRNA gene of IS1 shared 99% similarity with that of Alphaprotoebacterium BAL284, while IS2 scored 100% similarity with that of Pseudomonas putida 32zhy. Malathion residues almost completely disappeared within 6 days of incubation in IS2 liquid cultures. LC/ESI-MS analysis confirmed the degradation of malathion to malathion monocarboxylic and dicarboxylic acids, which formed as a result of carboxylesterase activity. A carboxylesterase gene (CE) was amplified from the IS2 genome by using specifically designed PCR primers. The sequence analysis showed a significant similarity to a known CE gene in different Pseudomonas sp. We report here the isolation of a new malathion-degrading bacteria from soils in Egypt that may be very well adapted to the climatic and environmental conditions of the country. We also report the partial cloning of a new CE gene. Due to their high biodegradation activity, the bacteria isolated from this work merit further study as potential biological agents for the remediation of soil, water, or crops contaminated with the pesticide malathion.