The cyanide-degrading bacterium Pseudomonas pseudoalcaligenes CECT 5344 uses cyanide and different metal-cyanide complexes as the sole nitrogen source. Under cyanotrophic conditions, this strain was able to grow with up to 100 μM mercury, which was accumulated intracellularly. A quantitative proteomic analysis by liquid chromatography-tandem mass spectrometry (LC-MS/MS) has been applied to unravel the molecular basis of the detoxification of both cyanide and mercury by the strain CECT 5344, highlighting the relevance of the cyanide-insensitive alternative oxidase CioAB and the nitrilase NitC in the tolerance and assimilation of cyanide, independently of the presence or absence of mercury. Proteins overrepresented in the presence of cyanide and mercury included mercury transporters, mercuric reductase MerA, transcriptional regulator MerD, arsenate reductase and arsenical resistance proteins, thioredoxin reductase, glutathione S-transferase, proteins related to aliphatic sulfonates metabolism and sulfate transport, hemin import transporter, and phosphate starvation induced protein PhoH, among others. A transcriptional study revealed that from the six putative merR genes present in the genome of the strain CECT 5344 that could be involved in the regulation of mercury resistance/detoxification, only the merR2 gene was significantly induced by mercury under cyanotrophic conditions. A bioinformatic analysis allowed the identification of putative MerR2 binding sites in the promoter regions of the regulatory genes merR5, merR6, arsR, and phoR, and also upstream from the structural genes encoding glutathione S-transferase (fosA and yghU), dithiol oxidoreductase (dsbA), metal resistance chaperone (cpxP), and amino acid/peptide extruder involved in quorum sensing (virD), among others. IMPORTANCE Cyanide, mercury, and arsenic are considered very toxic chemicals that are present in nature as cocontaminants in the liquid residues generated by different industrial activities like mining. Considering the huge amounts of toxic cyanide- and mercury-containing wastes generated at a large scale and the high biotechnological potential of P. pseudoalcaligenes CECT 5344 in the detoxification of cyanide present in these industrial wastes, in this work, proteomic, transcriptional, and bioinformatic approaches were used to characterize the molecular response of this bacterium to cyanide and mercury, highlighting the mechanisms involved in the simultaneous detoxification of both compounds. The results generated could be applied for developing bioremediation strategies to detoxify wastes cocontaminated with cyanide, mercury, and arsenic, such as those generated at a large scale in the mining industry.