Biofilms are aggregates of microorganisms embedded in an extracellular matrix comprised largely of exopolysaccharides (EPSs), nucleic acids, and proteins. Pseudomonas aeruginosa is an opportunistic human pathogen that is also a model organism for studying biofilms in the laboratory. Here, we define a novel program of biofilm development used by mucoid (alginate-overproducing) P. aeruginosa in the presence of elevated calcium. Calcium cations cross-link negatively charged alginate polymers, resulting in individual cells being suspended in an alginate gel. The formation of this type of structurally distinct biofilm is not reliant on the canonical biofilm EPS components Psl and Pel or the matrix protein CdrA. We also observed that mucoid P. aeruginosa biofilm cells do not have the typical elevated levels of the secondary messenger cyclic di-GMP (c-di-GMP), as expected of biofilm cells, nor does the overproduction of alginate rely on high c-di-GMP. This contrasts with nonmucoid biofilms in which the production of the matrix components Psl, Pel, and CdrA is positively regulated by elevated c-di-GMP. We further demonstrate that calcium-gelled alginate biofilms impede the penetration of the antibiotic tobramycin, thus protecting the biofilm community from antibiotic-mediated killing. Finally, we show that bacterial aggregates with a dispersed cell arrangement like laboratory-grown calcium-alginate biofilm structures are present in explanted cystic fibrosis (CF) lung samples. Our findings illustrate the diverse nature of biofilm formation and structure in P. aeruginosa.