In this paper, using a graphene-based metasurface, we demonstrate a unique design to develop a highly efficient, broadband, mid-infrared cross-polarization converter. The proposed graphene-based metasurface structure comprises periodical ϕ-shaped graphene on the top surface of a noble-metal-backed dielectric silicon dioxide (SiO2). The reported structure converts the incident linearly polarized wave into cross-polarized components with a peak polarization conversion ratio of more than 0.9 over a large band. Furthermore, the metasurface structure exhibits the full width at half-maximum bandwidth of 41.98% with respect to its center frequency of 5.98 THz. The physical insights behind electromagnetic polarization conversion are supported by field distributions and retrieved electromagnetic parameters. The structure works as a broadband cross-polarization converter up to 40° incident angle for both TE and TM polarizations. In addition, the structure is found to be as thin as ∼λ/6 with respect to lowermost frequency of the polarization conversion. The period of the unit cell is ∼λ/24 to support the fact that the structure can be treated as a metasurface.