The increasing prevalence of multi-drug-resistant (MDR) strains of Pseudomonas aeruginosa among critically ill humans is of significant concern. In the current study, we show that MDR clinical isolates of P. aeruginosa representing three distinct genotypes that display high virulence against intestinal epithelial cells, form novel appendage-like structures on their cell surfaces. These appendages contain PstS, an extracellular phosphate binding protein. Using anti-PstS antibodies, we determined that the PstS-rich appendages in MDR strains are involved in adherence to and disruption of the integrity of cultured intestinal epithelial cell monolayers. The outer surface-expressed PstS protein was also identified to be present in P. aeruginosa MPAO1, although to a lesser degree, and its role in conferring an adhesive and barrier disruptive phenotype against intestinal epithelial cells was confirmed using an isogenic DeltaPstS mutant. Formation of the PstS rich appendages was induced during phosphate limitation and completely suppressed in phosphate-rich media. Injection of MDR strains directly into the intestinal tract of surgically injured mice, a known model of phosphate limitation, caused high mortality rates (60%-100%). Repletion of intestinal phosphate in this model completely prevented mortality. Finally, significantly less outer surface PstS was observed in the MPAO1 mutant DeltaHxcR thus establishing a role for the alternative type II secretion system Hxc in outer surface PstS expression. Gene expression analysis performed by RT-PCR confirmed this finding and further demonstrated abundant expression of pstS analogous to pa5369, pstS analogous to pa0688/pa14-55410, and hxcX in MDR strains. Taken together, these studies provide evidence that outer surface PstS expression confers a highly virulent phenotype of MDR isolates against the intestinal epithelium that alters their adhesive and barrier disrupting properties against the intestinal epithelium.