For a long time, the issues of sexual orientation and gender identity have been restrained from entering the legal arena as being regarded as too radical. In today’s society, these issues warrant consideration in the context of international criminal law. Critically reflecting on the way of placing these grounds within the international criminal law framework, this paper tries to unpack the sheer possibility of addressing them within the core international crimes. Correctly defining terms such as “sexual orientation” and “gender” is not only germane, but also necessary for international criminal law to tackle them accordingly. By doing so, the power of legal argumentation in international criminal law for protecting sexual minorities is strengthened, but its boundaries and vulnerabilities are also exposed. This paper proposes that the described massive violation of the most fundamental human rights should be legally qualified as persecution. For protecting sexual minorities on an international criminal law scale, it is argued that we are not really “there” yet, but we might just be on the right track.