In the past decade, there has been an increasing interest in green supply chain management, which integrates environmental thinking into supply chain management. Assessing a supplier’s potential for improvement is very important when an organization wants to achieve certain environmental targets concerning their supply base, taking into account the limited resources available. In this paper, incorporating environmental evaluation criteria into a comprehensive supplier segmentation approach called ‘supplier potential matrix’ (SPM), a green supplier segmentation is proposed to segment the suppliers. Two overarching dimensions—supplier’s capabilities and supplier’s willingness—are used to evaluate the supplier’s green potential. The two dimensions are measured by multiple criteria. A sorting method called ELECTRE TRI-rC is used to solve the resulted multi-criteria decision-making problem. In order to make a more meaningful distinction, a simple method is also proposed to assess the suppliers with respect to the carbon footprint of the raw materials they supply. The results of this assessment are combined with the ones of the SPM, resulting in a more useful segmentation. The proposed model is applied to a sample containing the suppliers of a large international company.