Syntaxins are a family of membrane-anchored SNARE proteins that are essential components required for membrane fusion in eukaryotic intracellular membrane trafficking pathways. Syntaxins contain an N-terminal regulatory domain, termed the Habc domain that is not highly conserved at the primary sequence level but folds into a three-helix bundle that is structurally conserved among family members. The syntaxin Habc domain has previously been found to be structurally very similar to the GAT domain present in GGA family members and related proteins that are otherwise completely unrelated to syntaxins. Because the GAT domain has been found to be a ubiquitin binding domain we hypothesized that the Habc domain of syntaxins may also bind to ubiquitin. Here, we report that the Habc domain of syntaxin 3 (Stx3) indeed binds to monomeric ubiquitin with low affinity. This domain binds efficiently to K63-linked poly-ubiquitin chains within a narrow range of chain lengths but not to K48-linked poly-ubiquitin chains. Other syntaxin family members also bind to K63-linked poly-ubiquitin chains but with different chain length specificities. Molecular modeling suggests that residues of the GGA3-GAT domain known to be important for ionic and hydrophobic interactions with ubiquitin may have equivalent, conserved residues within the Habc domain of Stx3. We conclude that the syntaxin Habc domain and the GAT domain are both structurally and functionally related, and likely share a common ancestry despite sequence divergence. Binding of Ubiquitin to the Habc domain may regulate the function of syntaxins in membrane fusion or may suggest additional functions of this protein family.