A mutation in the mucA gene, which encodes a negative regulator of alginate production in Pseudomonas aeruginosa, is the main mechanism underlying the conversion to mucoidy in clinical isolates from patients with cystic fibrosis (CF). Here, we announce the draft genome sequence of the stable alginate-overproducing mucoid strain P. aeruginosa PAO581 with a mucA25 mutation, a derivative from the nonmucoid strains P. aeruginosa PAO381 and PAO1.