Pseudomonas aeruginosa has been identified as an important causative agent of airway infection, mainly in cystic fibrosis. This disease is characterized by defective mucociliary clearance induced in part by mucus hyper-production. Mucin is a major component of airway mucus and is heavily O-glycosylated, with a protein backbone. Airway infection is known to be established with bacterial adhesion to mucin. However, the genes involved in mucin degradation or utilization remain elusive. In this study, we sought to provide a genetic basis of P. aeruginosa airway growth by identifying those genes. First, using RNASeq analyses, we compared genome-wide expression profiles of PAO1, a prototype P. aeruginosa laboratory strain, grown in M9-mucin (M9M) and M9-glucose (M9G) media. Additionally, a PAO1 transposon (Tn) insertion mutants library was screened for mutants defective in growth in M9M medium. One mutant with a Tn insertion in the xcpU gene (PA3100) was determined to exhibit faulty growth in M9M medium. This gene contributes to the type II secretion system, suggesting that P. aeruginosa uses this secretion system to produce a number of proteins to break down and assimilate the mucin molecule. Furthermore, we screened the PAO1 genome for genes with protease activity. Of 13 mutants, one with mutation in PA3247 gene exhibited defective growth in M9M, suggesting that the PA3247-encoded protease plays a role in mucin utilization. Further mechanistic dissection of this particular process will reveal new drug targets, the inhibition of which could control recalcitrant P. aeruginosa infections.