The current state of robotics relies largely on hand designed morphologies and controllers. This paradigm of robotics is well suited for controlled and static environments like warehouses or factory floors, but this type of robot often fails to extrapolate to autonomous behaviors in unpredictable and dynamic environments. In contrast, biological animals have evolved to seamlessly interact with the uncertainty of the real world. They accomplish this feat, in part, through specialized and complex morphologies that employ compliant materials. In this work, I explore the interactions of autonomous embodied agents’ brains and bodies with each other, and with the outside environment, through the evolution of soft robot morphologies and controllers. These interactions are first explored by evolving robots that perform complex and effective behaviors without high-level controllers in order to demonstrate the potential of morphological computation in compliant bodies. The study of morphological computation is further explored by also demonstrating effective behavior in tasks which are unapproachable with traditional rigid body robots (like squeezing and folding oneself). The focus on morphologically-driven behaviors is extended by evolving soft robots with neural-esque spiking muscles and demonstrating the optimization of physically embodied information pathways, exemplify the continuum between morphologies and controllers in embodied systems. I then turn to the simultaneous optimization of complex morphologies and high-level controllers, using the theory of embodied cognition to hypothesize that the specialization of morphologies and controllers to one another has been hindering the evolution of complex embodied machines. Results here demonstrate that a proposed algorithm for “morphological innovation protection”, which temporarily reduces selection pressure on newly mutated morphologies to enable readaptation of the coupled brain-body systems, produces significantly more fit robots and allows for their sustained optimization over evolutionary time. Generalizing the above methods, the design automation techniques employed here also are applied to problems outside of soft robots – demonstrating the optimization of object topologies towards a desired mechanical resonance. I hope that the work described in this dissertation will help to inform the automated design of embodied machines, like robots, for engineering applications, while also contributing to the fundamental and general understanding of embodied intelligent agents, and their evolution in natural systems.