In fresh fish products, excessive loads of Pseudomonas can lead to their rapid spoilage. It is wise for Food Business Operators (FBOs) to consider its presence both in whole and prepared fish products. With the current study, we aimed to quantify Pseudomonas spp. in fresh fillets of Salmo salar, Gadus morhua and Pleuronectes platessa. For all three fish species, we detected loads of presumptive Pseudomonas no lower than 104–105 cfu/g in more than 50% of the samples. We isolated 55 strains of presumptive Pseudomonas and carried out their biochemical identification; 67.27% of the isolates were actually Pseudomonas. These data confirm that fresh fish fillets are normally contaminated with Pseudomonas spp. and the FBOs should add it as a “process hygiene criterion” according to EC Regulation n.2073/2005. Furthermore, in food hygiene, it is worth evaluating the prevalence of antimicrobial resistance. A total of 37 Pseudomonas strains were tested against 15 antimicrobials, and they all were identified as being resistant to at least one antimicrobial, mainly penicillin G, ampicillin, amoxicillin, tetracycline, erythromycin, vancomycin, clindamycin and trimethoprim. As many as 76.47% of Pseudomonas fluorescens isolates were multi-drug resistant. Our results confirm that Pseudomonas is becoming increasingly resistant to antimicrobials and thus should be continuously monitored in foods.