PA-IL is a galactophilic lectin that is found on the outer membrane of Pseudomonas aeruginosa. Pigeon ovalbumin (POA), a phosphoprotein, contains high levels of terminal Galα(1→4)Gal units. Thus, magnetic nanoparticles with immobilized POA can be used as affinity probes for P. aeruginosa, functioning via the recognition of galactophilic PA-IL. We fabricated POA-bound nanoparticles (NPs) by immobilizing POA onto the surface of core/shell magnetic iron oxide/alumina NPs via metal-phosphate chelation. We then used the generated NPs to probe target bacteria from complex samples. The trapped bacterial cells were characterized based on their mass peak profiles obtained from MALDI MS analyses. In addition, we confirmed the determination of P. aeruginosa using a proteomic strategy: combining the resultant MALDI MS/MS spectra of its tryptic digest with protein database searching. The feasibility of using this approach to rapidly characterize P. aeruginosa from clinical samples without the need to perform culturing steps was also demonstrated.