Teaching and learning are highly social activities. Seminal psychologists such as Vygotsky, Piaget, and Bandura have theorized that social interaction is a key mechanism in the process of learning and development. In particular, the benefits of peer interaction for learning and motivation in classrooms have been broadly demonstrated through empirical studies. Hence, it would be valuable if computer-based environments could support a mechanism for a peer interaction. Though no claim of peer equivalence is made, pedagogical agents as learning companions (PALs)—animated digital characters functioning to simulate human-peer-like interaction—might provide an opportunity to simulate such social interaction in computer-based learning. In this article we ground the instructional potential of PALs in several social-cognitive theories, including distributed cognition, social interaction, and Bandura’s social-cognitive theory. We discuss how specific concepts of the theories might support various instructional functions of PALs, acknowledging concepts that PALs cannot address. Based on the theoretical perspectives, we suggest key constituents for designing PALs that in human-peer interactions have proven significant. Finally, we review the current status of PAL research with respect to these constituents and suggest where further empirical research is necessary.