The graphite-water interface provides a unique environment for polypeptides that generally favors ordered structures more than in solution. Therefore, systems consisting of designed peptides and graphitic carbon might serve as a convenient medium for controlled self-assembly of functional materials. Here, we computationally designed cyclic peptides that spontaneously fold into a β-sheet-like conformation at the graphite-water interface and self-assemble, and we subsequently observed evidence of such assembly by atomic force microscopy. Using a novel protocol, we screened nearly 2000 sequences, optimizing for formation of a unique folded conformation while discouraging unfolded or misfolded conformations. A head-to-tail cyclic peptide with the sequence GTGSGTGGPGGGCGTGTGSGPG showed the greatest apparent propensity to fold spontaneously, and this optimized sequence was selected for larger scale molecular dynamics simulations, rigorous free-energy calculations, and experimental validation. In simulations ranging from hundreds of nanoseconds to a few microseconds, we observed spontaneous folding of this peptide at the graphite-water interface under many different conditions, including multiple temperatures (295 and 370 K), with different initial orientations relative to the graphite surface, and using different molecular dynamics force fields (CHARMM and Amber). The thermodynamic stability of the folded conformation on graphite over a range of temperatures was verified by replica-exchange simulations and free-energy calculations. On the other hand, in free solution, the folded conformation was found to be unstable, unfolding in tens of picoseconds. Intermolecular hydrogen bonds promoted self-assembly of the folded peptides into linear arrangements where the peptide backbone exhibited a tendency to align along one of the six zigzag directions of the graphite basal plane. For the optimized peptide, atomic force microscopy revealed growth of single-molecule-thick linear patterns of 6-fold symmetry, consistent with the simulations, while no such patterns were observed for a control peptide with the same amino acid composition but a scrambled sequence.