Pseudomonas fragi, Pseudomonas lundensis and members of the Pseudomonas fluorescens group may spoil Ultra High Temperature (UHT) treated milk and dairy products, due to the production of heat-stable proteases in the cold chain of raw milk. Since the aprX gene codes for a heat-resistant protease in P. fluorescens, the presence of this gene has also been investigated in other members of the genus. For this purpose an aprX-screening PCR test has been developed. Twenty-nine representatives of important milk Pseudomonas species and thirty-five reference strains were screened. In 42 out of 55 investigated Pseudomonas strains, the aprX gene was detected, which proves the potential of the aprX-PCR test as a screening tool for potentially proteolytic Pseudomonas strains in milk samples. An extensive study of the obtained aprX-sequences on the DNA and the amino acid level, however, revealed a large heterogeneity within the investigated milk isolates. Although this heterogeneity sets limitations to a general detection method for all proteolytic Pseudomonas strains in milk, it offers a great potential for the development of a multiplex PCR screening test targeting individual aprX-genes. Furthermore, our data illustrated the potential use of the aprX gene as a taxonomic marker, which may help in resolving the current taxonomic deadlock in the P. fluorescens group.