The problem of finding partners is to identify which entities (agents) can provide requested services from a group of entities. It can be found in open and distributed environments for such tasks as file sharing and resource allocation. Previous studies have shown that entities can refine and determine partners through measuring trust relationships, i.e., the beliefs of entities that others will accomplish a request for assigned services at hand. Entities dynamically change their beliefs through recalling their past experiences in order to quickly identify partners for new requests. This paper aims to observe whether those changes can enable entities efficiently find partners and hence provide services. To this end, we propose a dynamic network of trust-based entities. Then, we investigate the dynamics of its structure and efficiency in the above-mentioned aspects. Autonomy-Oriented Computing (AOC) is applied to observe how the dynamics emerge from local behaviors. A notion of autonomy is embodied in defining how entities activate their partner finding behaviors, whereas self-organization is realized to update the strength of trust relationships. Experimental results explicitly display a dynamic process of this network, changing from containing no link (trust relationship) to having some stable links. Specially, in this process, the efficiency gradually gets enhanced.