Aerosol-OT is a widely used anionic surfactant, and its lyotropic properties have been studied extensively. However, neat AOT is itself liquid crystalline. We carried out an X-ray study of neat AOT sodium salt, as well as of AOT-n-decyl-, n-dodecyl-, n-tetradecyl-, and n-hexadecylammonium salts. We confirm an earlier report that pure AOT forms a hexagonal columnar phase but propose a different packing model. This involves a relatively highly ordered structure with each column cross-section containing three tessellated molecules in the plane normal to the column axis. The structure is trigonal locally but hexagonal over the long-range. This mode of assembly is supported by electron density reconstruction and molecular modeling. At subambient temperatures, the AOT-alkylammonium complexes Cn-AOT, with n=10-16, also display a hexagonal columnar phase, but this is more disordered, and each column cross-section contains only two ion pairs. Unusually, molar enthalpy and entropy of the columnar-isotropic transition in Cn-AOT salts decrease with increasing n. This is attributed to a disproportionally high conformational disorder of the radial chains in the columnar phase, which is required for efficient space filling.