Pseudolysin is the most abundant protease secreted by Pseudomonas aeruginosa and is the major extracellular virulence factor of this opportunistic human pathogen. Pseudolysin destroys human tissues by solubilizing elastin. However, the mechanisms by which pseudolysin binds to and degrades elastin remain elusive. In this study, we investigated the mechanism of action of pseudolysin on elastin binding and degradation by biochemical assay, microscopy and site-directed mutagenesis. Pseudolysin bound to bovine elastin fibers and preferred to attack peptide bonds with hydrophobic residues at the P1 and P1’ positions in the hydrophobic domains of elastin. The time-course degradation processes of both bovine elastin fibers and cross-linked human tropoelastin by pseudolysin were further investigated by microscopy. Altogether, the results indicate that elastin degradation by pseudolysin began with the hydrophobic domains on the fiber surface, followed by the progressive disassembly of macroscopic elastin fibers into primary structural elements. Moreover, our site-directed mutational results indicate that five hydrophobic residues in the S1-S1’ sub-sites played key roles in the binding of pseudolysin to elastin. This study sheds lights on the pathogenesis of P. aeruginosa infection.