Education is reported to be in crisis. The needs and demands of learners are continuously evolving due to rapid changes in the socio-cultural and technological landscape, whereas pedagogy is slow to change. Institutions have been admonished that they need to encourage creativity and innovation in educational practices. Yet prior research shows that realising innovative pedagogical solutions is not easy for teachers because it involves complex dilemmas. This research investigated the experiences of tertiary level pedagogical innovators to identify dilemmas they encountered during the innovation process and the strategies they used to resolve them. Interviews were conducted, either face-to-face or via Skype, with 30 research participants. The participants were all tertiary-level teachers who had led a team-based pedagogical innovation project and who had published about the innovation in peer-reviewed academic journals. In order to explore experiences of innovators, each interview was used to generate a cognitive map, and then the individual maps were combined into an aggregate map using Decision Explorer. The aggregate map was then explored and analysed to identify the dilemmas of innovators and the strategies used to resolve them. These findings were then reviewed, interpreted and discussed in the light of relevant literature. Overall, the findings of this study reaffirm that pedagogical innovators encounter a range of dilemmas while realizing their innovations and the effective management of these dilemmas enables them to progress toward their intended pedagogical goals. Effective management usually involved the “through—through” thinking advocated by Trompenaars. The main contributions of this research are: the application of cognitive mapping to identification of dilemmas; the identification of thirteen distinct dilemmas that can be managed by educational institutions and innovative educators; and articulation of alternative ways of reconciling dilemmas. The findings may assist educators with choosing an appropriate course of action when facing a dilemma during their innovations.