Model microbial systems provide opportunity to understand the genetic bases of ecological traits, their evolution, regulation and fitness contributions. Experimental populations of Pseudomonas fluorescens rapidly diverge in spatially structured microcosms producing a range of surface-colonising forms. Despite divergent molecular routes, wrinkly spreader (WS) niche specialist types overproduce a cellulosic polymer allowing mat formation at the air-liquid interface and access to oxygen. Given the range of ways by which cells can form mats, such phenotypic parallelism is unexpected. We deleted the cellulose-encoding genes from the ancestral genotype and asked whether this mutant could converge on an alternate phenotypic solution. Two new traits were discovered. The first involved an exopolysaccharide encoded by pgaABCD that functions as cell-cell glue similar to cellulose. The second involved an activator of an amidase (nlpD) that when defective causes cell chaining. Both types form mats, but were less fit in competition with cellulose-based WS types. Surprisingly, diguanylate cyclases linked to cellulose overexpression underpinned evolution of poly-beta-1,6-N-acetyl-d-glucosamine (PGA)-based mats. This prompted genetic analyses of the relationships between the diguanylate cyclases WspR, AwsR and MwsR, and both cellulose and PGA. Our results suggest that c-di-GMP regulatory networks may have been shaped by evolution to accommodate loss and gain of exopolysaccharide modules facilitating adaptation to new environments.