Crystal structure predictions of Na x C6O6 (x =2.5, 3, 3.5, and 4) have been carried out using first-principles calculations in conjunction with an evolutionary algorithm to understand charge/discharge mechanisms in the Na x C6O6 cathode of organic-based sodium-ion batteries. We predict a new stacking of C6O6 molecules that is different from the well-known stacking of Na2C6O6. Calculated voltages of the Na x C6O6 battery as a function of x with the new C6O6 stacking are consistent with experimental results. The electronic structure analyses show that the intermolecule bonding and antibonding states of C6O6 have important roles on the battery reaction mechanism.