The Rome Statute of the International Criminal Court (ICC) includes gender justice provisions, notably the recognition of crimes of sexual violence experienced by women in armed conflict. The Statute also institutes a complementarity regime, leaving states parties with primary responsibility for prosecuting international crimes. However, it fails to link these two innovative provisions, leaving a ‘gender justice complementarity shadow.’ Through an analysis of ICC preliminary examinations in Guinea and Colombia, this article argues that the Office of the Prosecutor’s apparent inattention to gender biases underpinning domestic legal systems has left impunity for perpetrators of sexual violence intact and the victims of these crimes unrecognized. It argues that to tackle impunity for sexual violence through complementarity requires the ICC prosecutor to include an examination of gender biases in domestic legal systems when testing state action, willingness and ability in order to understand how these biases impede access to justice for victims of sexual violence.