Pseudomonas aeruginosa, one of the most intractable Gram-negative bacteria, has become a public health threat due to its outer polysaccharide layer, efflux transporter system, and high level of biofilm formation, all of which contribute to multi-drug resistance. Even though it is a pathogen of the highest concern, the status of the antibiotic development pipeline is unsatisfactory. In this review, we summarize marine natural products (MNPs) isolated from marine plants, animals, and microorganisms which possess unique structures and promising antibiotic activities against P. aeruginosa. In the last decade, nearly 80 such MNPs, ranging from polyketides to alkaloids, peptides, and terpenoids, have been discovered. Representative compounds exhibited impressive in vitro anti-P. aeruginosa activities with MIC values in the single-digit nanomolar range and in vivo efficacy in infectious mouse models. For some of the compounds, the preliminary structure-activity-relationship (SAR) and anti-bacterial mechanisms of selected compounds were introduced. Compounds that can disrupt biofilm formation or membrane integrity displayed potent inhibition of multi-resistant clinical P. aeruginosa isolates and could be considered as lead compounds for future development. Challenges on how to translate hits into useful candidates for clinical development are also proposed and discussed.