In this study, we reported the phytochemical composition of the aerial parts of Atriplex halimus L. collected from Sardinia. This species is a halophytic shrub, typical of the Mediterranean Basin. Four new glycosylated flavonoids were isolated and their structures were elucidated on the basis of 1D, 2D NMR and MS spectra as 3',5'-dimethoxymyricetin-3-O-β-D-xylopyranosyl-7-O-fucopyranosyl-(1 → 3)-β-D-glucopyranoside (1), 3'-methoxyquercetin-7-O-β-D-fucopyranosyl-(1 → 3)-β-d-glucopyranosyl-3-O-β-xylopyranosyl-(1 → 4)-β-xylopyranoside (2), 3'-methoxyquercetin-7-O-α-l-rhamnopyranosyl-3-O-α-arabinofuranosyl-(1 → 6)-β-D-glucopyranoside (3) and 3',5'-dimethoxymyricetin-7-O-fucopyranosyl-(1 → 3)-β-D-glucopyranoside (4). LC-MS(n) analysis on the extract revealed the presence of other myricetin, quercetin, isorhamnetin glycosides, simple phenolic acids and esters.