Nature-based early childhood education (NBECE) is a growing field for children aged 3-6 in North America. This growth demands the need for NBECE professionals. Often grounded in personal journey and perceptions, pedagogical practices of NBECE teachers play a vital role in learning experiences and nature-connectedness. This qualitative research delves into North American NBECE professionals' perceptions of nature, their journey into NBECE, and their responses to the pervasive influence of settler-colonial values in education. The data was generated through teacher interviews with four outdoor preschool teachers. Each teacher participated in two interviews. Between the two interviews they wrote a journal entry. At the end of the second interview, I led each participant through a cognitive mapping exercise in which they created a visual representation of their journey with nature. Findings indicated that these teachers have a close connection and history with nature. This often translated into their feelings about NBECE. Framed within settler-colonial studies, I deconstructed teachers' discussions to illuminate examples of resisting a nature-culture divide and human exceptionalism. I identified most teachers exhibiting awareness of settler-colonialism, with more experienced teachers thoroughly exploring their connection to its ongoing influence.