In 1882, Elie Metchnikoff identified myeloid-like cells from starfish larvae responding to the invasion by a foreign body (rose thorn). This marked the origins for the study of innate immunity, and an appreciation that cellular immunity was well established even in these "primitive" organisms. This chapter focuses on these myeloid cells as well as the newest members of this family, the dendritic cells, and explores their evolutionary origins. Our goal is to provide evolutionary context for the development of the multilayered immune system of mammals, where myeloid cells now serve as central effectors of innate immunity and regulators of adaptive immunity. Overall, we find that core contributions of myeloid cells to the regulation of inflammation are based on mechanisms that have been honed over hundreds of millions of years of evolution. Using phagocytosis as a platform, we show how fairly simple beginnings have offered a robust foundation onto which additional control features have been integrated, resulting in central regulatory nodes that now manage multifactorial aspects of homeostasis and immunity.