Myxococcus xanthus moves by gliding motility powered by Type IV pili (S-motility) and a second motility system, A-motility, whose mechanism remains elusive despite the identification of approximately 40 A-motility genes. In this study, we used biochemistry and cell biology analyses to identify multi-protein complexes associated with A-motility. Previously, we showed that the N-terminal domain of FrzCD, the receptor for the frizzy chemosensory pathway, interacts with two A-motility proteins, AglZ and AgmU. Here we characterized AgmU, a protein that localized to both the periplasm and cytoplasm. On firm surfaces, AgmU-mCherry colocalized with AglZ as distributed clusters that remained fixed with respect to the substratum as cells moved forward. Cluster formation was favoured by hard surfaces where A-motility is favoured. In contrast, AgmU-mCherry clusters were not observed on soft agar surfaces or when cells were in large groups, conditions that favour S-motility. Using glutathione-S-transferase affinity chromatography, AgmU was found to interact either directly or indirectly with multiple A-motility proteins including AglZ, AglT, AgmK, AgmX, AglW and CglB. These proteins, important for the correct localization of AgmU and AglZ, appear to be organized as a motility complex, spanning the cytoplasm, inner membrane and the periplasm. Identification of this complex may be important for uncovering the mechanism of A-motility.