Valley-filling deposits of the Nama Group, southern Namibia, record two episodes of erosional downcutting and backfill, developed close together in time near the Ediacaran-Cambrian boundary. Geochronological constraints indicate that the older valley fill began 539.4 ± 1 Ma or later; the younger of these deposits contains unusually well-preserved populations of the basal Cambrian trace fossil Treptichnus pedum. Facies analysis shows that T. pedum is closely linked to a nearshore sandstone deposit, indicating a close environmental or taphonomic connection to very shallow, mud-draped sandy seafloor swept by tidal currents. Facies restriction may limit the biostratigraphic potential of T. pedum in Namibia and elsewhere, but it also illuminates functional and ecological interpretation. The T. pedum tracemaker was a motile bilaterian animal that lived below the sediment-water interface—propelling itself forward in upward-curving projections that breached the sediment surface. The T. pedum animal, therefore, lived infaunally, perhaps to avoid predation, surfacing regularly to feed and take in oxygen. Alternatively, the T. pedum animal may have been a deposit feeder that surfaced largely for purposes of gas exchange, an interpretation that has some support in the observed association of T. pedum with mud drapes. Treptichnus pedum provides our oldest record of animals that combined anatomical and behavioral complexity. Insights from comparative biology suggest that basal Cambrian T. pedum animals already possessed the anatomical, neurological, and genetic complexity needed to enable the body plan and behavioral diversification recorded by younger Cambrian fossils.