Paracoccus denitrificans is a non-swimming Gram-negative bacterium, with versatile respiration capability which has remarkable potentials for bioremediation, especially in water treatment. Although biofilms are important in water treatment systems, the genetic mechanisms underlying the cellular adherence and biofilm formation of this bacterium remain unknown. We show that P. denitrificans forms a thin biofilm on surfaces at the air-liquid interface under static conditions. The initial step of biofilm formation requires a biofilm-associated protein BapA, which we identified by transposon mutant screening. BapA contains a unique sequence of dipeptide repeats of aspartate and alanine. Our data indicate that BapA is translocated to the extracellular milieu by a type 1 secretion system, where it enables the cells to attach to the substratum. Furthermore, superresolution microscopy shows that BapA is localized on the cell surface, which alters the cell surface hydrophobicity. Our results show a crucial role of BapA that promotes the adhesion and biofilm formation of P. denitrificans.