The study examines implementation of a re-branding campaign in a public Canadian university.  The study is theoretically positioned in the intersection of the academic literature on re-branding, internal branding and the dilemma approach where a novel interlocked conceptual framework is presented. The data of the study comprise 19 qualitative semi-structured interviews with internal stakeholders of the university. Four core dilemma pairs were found emerging from the data: 1) new brand vs. old brand; 2) departmental marketing vs. centred marketing; 3) formal message vs. informal message; 4) attracting students to on campus education vs. attracting students to virtual on-line education. Thus, this study reveals implementing a re-branding campaign in higher education is about embracing the world of dilemmas by involving and empowering employees in reconciliation of the dilemmas. Co-reconciliation of the detected brand-related dilemmas, with and by employees, can be implemented by involving employees in the process of rebranding from the beginning. Indeed, this paper suggests that the preparedness to detect and address dilemmas is core to successful re-branding. Consequently, our results indicate that traditional change management approaches produce unreconciled dilemmas, which hinder the implementation of the new brand.  It is argued that employee participation in re-branding does not build employee supportiveness towards the new brand unless the core dilemmas are reconciled. It is also argued, that rebranding in a higher education institution without thorough internal branding faces the traditional dilemmas: simply imposing branding makes little difference in implementing the new changes.