The period of exploration of North America by various European nations manifested an intense moment of cultural, political, economic, and environmental change. Often marked by violence, Europeans failed to understand the gendered practices of the Indigenous population, which often liberated women from the confines of marriage and allowed for a spectrum of sexual identities and practices. European explorers, endowed with a sense of masculine dominance, given their role as captains or brave soldiers, confronted not only a vastly different gendered terrain and site of sexual fluidity but their own masculinity struggles with Indigenous men. As Europeans imposed religious mores and situated European customs as civilized and superior, explorers and settlers disrupted Native identities and power structures. This chapter asserts that the various conflicts and challenges encountered within the landscape of the New World can and should be considered through the lens of eroticization, sexuality, and gender. Often these contests of power disadvantaged women and sexualities that failed to conform to Christianity. These literal and psychological sites of struggle laid the foundation for future colonization and dramatically impacted and altered understandings of the colonial experiment.