Pseudomonas aeruginosa is an important opportunistic pathogen that produces a large arsenal of small molecule virulence factors and quorum sensing signal molecules. The annotation of these secondary metabolites in untargeted, mass spectrometry-based metabolomics is difficult, as many of them cannot be found in common metabolite databases, and as manual annotation is tedious. We therefore developed an algorithm named CluMSID that uses cosine similarities of product ion spectra and neutral loss patterns in combination with unsupervised clustering methods such as multidimensional scaling, density based clustering and hierarchical clustering to group structurally similar compounds and hence facilitate their annotation. The use of this tool allowed us to find clusters for several classes of primary and secondary metabolites, and helped identifying spectral similarities that would have gone unnoticed in standard untargeted metabolomics data analysis workflows. CluMSID enabled the annotation of 27 previously undescribed members of the canonical classes of alkyl quinolone quorum sensing signal molecules and provided evidence for the postulation of a new putative alkyl quinolone class. The CluMSID script written in R is open source and can be used by anyone in the metabolomics and natural product research community.