We have grown single crystals of Na$_x$Ca$_y$CoO$_2$ and determined their superstructures as a function of composition using neutron and x-ray diffraction. Inclusion of Ca$^{2+}$ stabilises a single superstructure across a wide range of temperatures and concentrations. The superstructure in the Na$^+$ layers is based on arrays of divacancy clusters with Ca$^{2+}$ ions occupying the central site, and it has an ideal concentration Na$_{4/7}$Ca$_{1/7}$CoO$_2$. Previous measurements of the thermoelectric properties on this system are discussed in light of this superstructure. Na$_{4/7}$Ca$_{1/7}$CoO$_2$ corresponds to the maximum in thermoelectric performance of this system.