The statistical thermodynamics of a binary honeycomb-lattice gas is studied. The possible ordered distributions of substitutional atoms over the sites are predicted and a problem of their stability is analyzed. The ranges of values of interatomic-interaction parameters providing the low-temperature stability of the honeycomb-lattice-based superstructures at different stoichiometries are calculated within the scope of the third-nearest-neighbor Ising model and more realistic all-coordination-shell-interaction model. The first model results in the instability of some predicted superstructures, while the second model shows that each of them is stable at the certain values of interatomic-interaction energies. Even short-range interatomic interactions provide a stability of some superstructures, while only long-range interactions stabilize other ones. (C) 2010 Professor T. Nejat Veziroglu. Published by Elsevier Ltd. All rights reserved.