Plant type II arabinogalactan (AG) polysaccharides are attached to arabinogalactan proteins (AGPs) at hydroxyproline residues, and they are very diverse and heterogeneous structures. The AG consists of a β-(1 → 3)-linked galactan backbone with β-(1 → 6)-galactan side chains that are modified mainly with arabinose, but they may also contain glucuronic acid, rhamnose or other sugars. Here, we studied the positions of fucose substitutions in AGPs, and we investigated the functions of this fucosylation. Monosaccharide analysis of Arabidopsis leaf AGP extracts revealed a significant reduction in L-Fucose content in the fut4 mutant, but not in the fut6 mutant. In addition, Fucose was reduced in the fut4 mutant in root AGP extracts and was absent in the fut4/fut6 mutant. Curiously, in all cases reduction of fucose was accompanied with a reduction in xylose levels. The fucosylated AGP structures in leaves and roots in wild type and fut mutant plants were characterised by sequential digestion with AG specific enzymes, analysis by Polysaccharide Analysis using Carbohydrate gel Electrophoresis, and Matrix Assisted Laser Desorption/Ionisation (MALDI)-Time of Flight Mass spectrometry (MS). We found that FUT4 is solely responsible for the fucosylation of AGPs in leaves. The Arabidopsis thaliana FUT4 and FUT6 genes have been previously proposed to be non-redundant AG-specific fucosyltransferases. Unexpectedly, FUT4 and FUT6 enzymes both fucosylate the same AGP structures in roots, suggesting partial redundancy to each other. Detailed structural characterisation of root AGPs with high energy MALDI-Collision Induced Dissociation MS and NMR revealed an abundant unique AG oligosaccharide structure consisting of terminal xylose attached to fucose. The loss of this structure in fut4/fut6 mutants explains the reduction of both fucose and xylose in AGP extracts. Under salt-stress growth conditions the fut4/fut6 mutant lacking AGP fucosylation exhibited a shorter root phenotype than wild type plants, implicating fucosylation of AGPs in maintaining proper cell expansion under these conditions.