Discovering and matching services among heterogeneous agents is the fundamental process for agent cooperation and coordination in multi-agent systems. In such a process, numerous service-providing agents are matched against requested criteria. During the matching procedure, an agent is given the chance to discover its new corresponding agents that can provide desirable services. However, in order to solve more complex problems, the number of agents in a multi-agent system is increasing rapidly; therefore making the chance for an efficient and desirable match is decreased. Thus, improving the efficiency of the agent matching process has become an important issue in the multi-agent filed. Utilising an appropriate agent-matching mechanism will enhance agent cooperation and communication efficiency in dealing with complex problems. In this chapter, we develop a new agent-matching algorithm, the Agent-Rank (AR hereafter) algorithm, which ranks service-providing agents according to their contributions to a nominated requesting agent. The AR algorithm improves agent matching process through combining the general ranking scores with the request-based ranking scores. The AR algorithm narrows down the searching targets (services), which is avail to detect some random targets in a chance discovery process.