We analyze the dynamics of post-glacial coastal margin (CM) productivity and explore how it affected the emergence of six complex CM societies. Following deglaciation, global relative sea level stabilized after ~7000 BP and CM productivity significantly increased in many areas. Primary and secondary productivity (fish) likely increased by an order of magnitude or more. Aquatic animals were readily available in the CM providing sources of polyunsaturated omega-3 fatty acids, high-quality protein, and nutrients, especially essential to human nutrition. In all six case studies, mature CMs appear to have been occupied by Neolithic agricultural and fishing villages within ~500 years of sea-level stabilization. Within a few hundred years population densities increased and roughly a millennium later social ranking and monumental architecture appeared. Sea-level stabilization and increased CM productivity in conjunction with agricultural intensification in lower alluvial floodplains were major contributors to the origins of many complex CM societies.