Cyclic di-GMP (c-di-GMP) is a novel secondary-messenger molecule that is involved in regulating a plethora of important bacterial activities through binding to an unprecedented array of effectors. Proteins with a canonical PilZ domain that bind c-di-GMP play crucial roles in regulating flagellum-based motility. In contrast, noncanonical type II PilZ domains that do not effectively bind c-di-GMP regulate twitching motility, which is dependent on type IV pili (T4P). Recent data indicate that T4P biogenesis is initiated via the interaction of a noncanonical type II PilZ protein with the GGDEF/EAL-domain protein FimX and the pilus motor protein PilB at high c-di-GMP concentrations. However, the molecular details of such interactions remain to be elucidated. In this manuscript, the first hetero-complex crystal structure between a type II PilZ protein and the EAL domain of the FimX protein (FimX(EAL)) from Xanthomonas campestris pv. campestris (Xcc) in the presence of c-di-GMP is reported. This work reveals two novel conformations of monomeric c-di-GMP in the XccFimX(EAL)-c-di-GMP and XccFimX(EAL)-c-di-GMP-XccPilZ complexes, as well as a unique interaction mode of a type II PilZ domain with FimX(EAL). These findings indicate that c-di-GMP is sufficiently flexible to adjust its conformation to match the corresponding recognition motifs of different cognate effectors. Together, these results represent a first step towards an understanding of how T4P biogenesis is controlled by c-di-GMP at the molecular level and also of the ability of c-di-GMP to bind to a wide variety of effectors.