It is well known that flagellated bacteria swim in circles near surfaces. However, recent experiments have shown that a sulfide-oxidizing bacterium named Thiovulum majus can transition from swimming in circles to a surface bound state where it stops swimming while remaining free to move laterally along the surface. In this bound state, the cell rotates perpendicular to the surface with its flagella pointing away from it. Using numerical simulations and theoretical analysis, we demonstrate the existence of a fluid-structure interaction instability that causes cells with relatively short flagella to become surface bound.