This narrative review article contributes to the discussion on destination sustainability by focusing on cruise tourism practices. Cruise tourism is a complex industry, particularly from a destination perspective. There have been many calls for cruise tourism to become more sustainable for destinations but little consensus about what this means, or how it could be achieved. The aim of this article is to review the literature on cruise tourism destinations and to unpack the ways in which sustainability issues are framed at destination level. We have reviewed 98 peer-reviewed empirical journal articles (2015–2022). The article shows how the research literature on cruise tourism and sustainability issues has evolved over 7 years, which aspects of sustainability are considered to be most important and/or problematic and what solutions are suggested to improve the sustainability of cruise tourism. We develop three critical avenues towards sustainable cruise destinations: 1) from specific outcomes to the interconnectedness of desired practices, 2) alternatives to the growth paradigm, and 3) governing for coexistence and the commons. These critical avenues are based on the discussion of what sustainability means for cruise destinations, and translates these into pathways of future research.