Gram-negative bacteria use the sophisticated type II secretion system (T2SS) to secrete a large number of exoproteins into the extracellular environment. Five proteins of the T2SS, the pseudopilins GspG-H-I-J-K, are proposed to assemble into a pseudopilus involved in the extrusion of the substrate through the outer membrane channel. Recent structural data have suggested that the three pseudopilins GspI-J-K are organized in a trimeric complex located at the tip of the GspG-containing pseudopilus. In the present work we combined two biochemical techniques to investigate the protein-protein interaction network between the five Pseudomonas aeruginosa Xcp pseudopilins. The soluble domains of XcpT-U-V-W-X (respectively homologous to GspG-H-I-J-K) were purified, and the interactions were tested by surface plasmon resonance and affinity co-purification in all possible combinations. We found an XcpV(I)-W(J)-X(K) complex, which demonstrates that the crystallized trimeric complex also exists in the P. aeruginosa T2SS. Interestingly, our systematic approach revealed an additional and yet uncharacterized interaction between XcpU(H) and XcpW(J). This observation suggested the existence of a quaternary, rather than ternary, complex (XcpU(H)-V(I)-W(J)-X(K)) at the tip of the pseudopilus. The assembly of this quaternary complex was further demonstrated by co-purification using affinity chromatography. Moreover, by testing various combinations of pseudopilins by surface plasmon resonance and affinity chromatography, we were able to dissect the different possible successive steps occurring during the formation of the quaternary complex. We propose a model in which XcpV(I) is the nucleator that first binds XcpX(K) and XcpW(J) at different sites. Then the ternary complex recruits XcpU(H) through a direct interaction with XcpW(J).