Fourteen psychrotolerant Pseudomonas strains were isolated from seawater and sediments in the Mediterranean Sea, Egypt, using culture-dependent techniques. Genotypic characterization for the fourteen strains was performed using 16S rDNA sequence analysis. The Pseudomonas strains were screened for some physiological, and biochemical characters, also resistance to some antibiotics and heavy metals were tested. Moreover, heavy metals bioaccumulation and azo-dyes removal were estimated. All tested Pseudomonas strains were able to resist and accumulate several metals (Pb²+, Cu²⁺ and Cd²⁺) with variable degrees, depending on bacterial strains and metal ion species. The highest tolerance (MICs) was observed with lead ions as all strains grew in presence of 750-800 ppm of lead, also, lead ions were easier to bioaccumulate than the other metals, while cadmium bioaccumulation was relatively low with respect to the other two metals. Pseudomonas sp.H69A was the most potent strain in the accumulation of different metals. It supports the highest accumulated values of lead and cupper (2.95 and 1.837 mg /g fresh cells, respectively). The Pseudomonas strains were monitored for their ability to decolorize three different azo-dyes (fast orange, methanil yellow and acid-fast red). All Pseudomonas strains achieved powerfull decolorization activity with the tested dyes. The maximum decolorization activities were recorded in fast orange. Pseudmonas sp. H26S recorded the highest decolorization percentages (91%) with fast orange and their biosorption capacity was 4.8 mg/g.