We previously screened the novel gene Ds-26-16 from a 4 M salt-stressed Dunaliella salina cDNA library and discovered that this gene conferred salt tolerance to broad-spectrum organisms, including E. coli (Escherichia coli), Haematococcus pluvialis and tobacco. To determine the mechanism of this gene conferring salt tolerance, we studied the proteome of E. coli overexpressing the full-length cDNA of Ds-26-16 using the iTRAQ (isobaric tags for relative and absolute quantification) approach. A total of 1,610 proteins were identified, which comprised 39.4% of the whole proteome. Of the 559 differential proteins, 259 were up-regulated and 300 were down-regulated. GO (gene ontology) and KEGG (Kyoto encyclopedia of genes and genomes) enrichment analyses identified 202 major proteins, including those involved in amino acid and organic acid metabolism, energy metabolism, carbon metabolism, ROS (reactive oxygen species) scavenging, membrane proteins and ABC (ATP binding cassette) transporters, and peptidoglycan synthesis, as well as 5 up-regulated transcription factors. Our iTRAQ data suggest that Ds-26-16 up-regulates the transcription factors in E. coli to enhance salt resistance through osmotic balance, energy metabolism, and oxidative stress protection. Changes in the proteome were also observed in E. coli overexpressing the ORF (open reading frame) of Ds-26-16. Furthermore, pH, nitric oxide and glycerol content analyses indicated that Ds-26-16 overexpression increases nitric oxide content but has no effect on glycerol content, thus confirming that enhanced nitric oxide synthesis via lower intercellular pH was one of the mechanisms by which Ds-26-16 confers salt tolerance to E. coli.