Gas Vesicles (GVs) are gas-filled protein nanostructures employed by several species of bacteria and archaea as flotation devices to enable access to optimal light and nutrients. The unique physical properties of GVs have led to their use as genetically-encodable contrast agents for ultrasound and MRI. Currently, however, the structure and assembly mechanism of GVs remain unknown. Here we employ cryo-electron tomography to reveal how the GV shell is formed by a helical filament of highly-conserved GvpA subunits. This filament changes polarity at the center of the GV cylinder, a site that may act as an elongation center. High-resolution subtomogram averaging reveals a corrugated pattern of the shell arising from polymerization of GvpA into a β-sheet. The accessory protein GvpC forms a helical cage around the GvpA shell, providing reinforcement. Together, our results help explain the remarkable mechanical properties of GVs and their ability to adopt different diameters and shapes.