Scanning tunneling microscopy is used to monitor the formation and relaxation of nanoprotrusions and nanoindentations at extended step edges following submonolayer deposition of Ag on Ag(100). Deposition of up to about 1/4 ML Ag produces isolated two-dimensional (2D) Ag clusters, which subsequently diffuse, collide, and coalesce with extended step edges, thus forming protrusions. Deposition of larger submonolayer amounts of Ag causes existing step edges to advance across terraces, incorporating 2D islands. The resulting irregular step structure rapidly straightens after terminating deposition, except for a few larger indentations. Relaxation of these far-from-equilibrium step-edge nanoconfigurations is monitored to determine rates for restructuring versus local geometry and feature size. This behavior is analyzed utilizing kinetic Monte Carlo simulations of an atomistic lattice-gas model for relaxation of step-edge nanostructures. In this model, mass transport is mediated by diffusion along the step edge (i.e., “periphery diffusion”). The model consistently fits observed behavior, and allows a detailed characterization of the relaxation process, including assessment of key activation energies.