We investigate rocky coastline evolution over millennial time scales using exploratory analytical and numerical models based on interactions between beaches and sea cliffs. In the models, wave-driven sea-cliff retreat is a nonlinear function of beach width, where cliff retreat is maximized by sediment abrasion and minimized by either a lack of beach sediment or too much sediment (which prevents waves from reaching the sea cliff). As sea cliffs retreat, beach sediment is produced and distributed alongshore by wave-driven sediment transport, and local beach widths determine future cliff retreat rates. Numerical experiments indicate that through such interactions, rocky coastlines can reach an equilibrium configuration where headlands and embayments remain stable through time, even in the absence of alongshore variations in sea-cliff lithology. Furthermore, the equilibrium coastline configuration, or the alongshore proportion of rocky headland to cliff-backed pocket beach, can be predicted analytically. Initial tests suggest that predictions match well qualitatively with actual landscapes.