With the wide adoption of Open Grid Services Architecture (OGSA) and Web Services Resource Framework (WSRF), the Grid is emerging as a service-oriented computing infrastructure for engineers and scientists to solve data and computationally intensive problems. It is envisioned that computing resources in a future Grid environment will be exposed as services. Service discovery becomes an issue of vital importance for a wider uptake of the Grid. This paper presents RSSM, a Rough Sets based service matchmaking algorithm for service discovery with an aim to tolerate uncertainty in identifying service properties. The evaluation results show that the RSSM algorithm is more effective in service discovery compared with other mechanisms such as UDDI and OWL-S.