This paper scrutinizes a set of paradoxes arising from a mismatch between contemporary discourses that praise and promote mobility in and internationalization of higher education, and the everyday effects of mobility and internationalization on university teaching and learning practice. We begin with a general characterization of the discourse of mobility and internationalization in a European context and then turn to Denmark as a specific case in which we unfold and discuss three paradoxes in turn: internationalization and linguistic pluralism, internationalization and intercultural understanding and, finally, internationalization and competitiveness. We then link our deconstruction of the three paradoxes to a critique of the concept of "parallel language policy," widely promoted in the Nordic context, and show how it potentially undermines the ideals of internationalization.