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 are one of the most contemporary ones and warrant our consideration in the context of international criminal law. Critically reflecting on the way, but also the possibility of placing these grounds within the framework of the Rome Statute, this paper tries to unpack the sheer possibility of addressing these grounds within the crimes of genocide and persecution, as a crime against humanity. By subsuming sexual orientation under the definition of gender as it stands in the Rome Statute, as well as considering them independently, persecution on the grounds of sexual orientation and gender identity is argued as a crime against humanity. 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 shown. Aware of the current situation in the Republic of Chechnya, this paper proposes that national legislation which criminalizes same-sex conduct and the described massive violation of the most fundamental human rights should be legally qualified as a crime against humanity and a missed opportunity for the International Criminal Court. These legal constraints that engulf the sphere of international criminal law are tackled by referring to the Alien Tort Claims Act (ATCA). Within the purview of the ATCA, by reflecting on the SMUG v. Lively case, an alternative possibility of protecting sexual minorities from possible gross violations of their human rights is discussed. For protecting sexual minorities on a international criminal law scale, this paper advocates that we are not really ‘there’ yet, but we might just be on the right track. By correctly defining the term gender, by recognizing the potential of open clauses under the ICC Statute, qualifying domestic criminalization of same-sex conduct as a crime against humanity and tackling legal circumvention appropriately, a human security approach with regards to sexual orientation and gender identity would be ensured in international criminal law. Accordingly, this paper calls for a consideration to properly address the issues of sexual orientation and gender as essential for the future prevention of mass atrocities.