Casuarina glauca displays high levels of salt tolerance, but very little is known about how this tree adapts to saline conditions. To understand the molecular basis of C. glauca response to salt stress, we have analyzed the proteome from branchlets of plants nodulated by nitrogen-fixing Frankia Thr bacteria (NOD+) and non-nodulated plants supplied with KNO3 (KNO3+), exposed to 0, 200, 400, and 600 mM NaCl. Proteins were identified by Short Gel, Long Gradient Liquid Chromatography coupled to Tandem Mass Spectrometry and quantified by Sequential Window Acquisition of All Theoretical Mass Spectra -Mass Spectrometry. 600 proteins were identified and 357 quantified. Differentially Expressed Proteins (DEPs) were multifunctional and mainly involved in Carbohydrate Metabolism, Cellular Processes, and Environmental Information Processing. The number of DEPs increased gradually with stress severity: (i) from 7 (200 mM NaCl) to 40 (600 mM NaCl) in KNO3+; and (ii) from 6 (200 mM NaCl) to 23 (600 mM NaCl) in NOD+. Protein–protein interaction analysis identified different interacting proteins involved in general metabolic pathways as well as in the biosynthesis of secondary metabolites with different response networks related to salt stress. Salt tolerance in C. glauca is related to a moderate impact on the photosynthetic machinery (one of the first and most important stress targets) as well as to an enhancement of the antioxidant status that maintains cellular homeostasis.