Identification of polluting vehicles, which are emitting exhaust gases more than the permissible limits, is one of the major challenges in urban areas. The paper highlights the identification and therefore, prioritization of polluting vehicle fleets. A remote sensing device (RSD) database of around 500,000 vehicles, which are randomly screened for pollution check over one year in the Kolkata Metropolitan Area (KMA), India, is utilized. Applying cross-classification, the number of polluting vehicles per 1000 vehicles (polluting rate) is estimated for vehicle fleets based on vehicle characteristics such as vehicle age, vehicle class, emission norms, fuel type. A K-Means clustering technique is employed to prioritize the polluting vehicle fleets considering the polluting rate as well as the number of vehicle trips observed by RSD for the corresponding fleet. A four-quadrant decision space is created to prioritize the clusters with “high polluting rate and more number of vehicle trips.” The prioritization of such clustered polluting fleets for pollution checks shall lead to the identification of more polluting vehicles compared to the standard random intercept approach. The approach demonstrated here shows that screening only 44–46% of vehicle trips which includes trips in prioritized clusters leads to capturing more than 74–80% of the polluting vehicles. To conclude, the resources used to screen all vehicle fleets may be suitably used to refine the existing screening strategy (random intercepts) to screen prioritized polluting vehicle fleets.