The agent based approach is a well established methodology to model distributed intelligent systems. Multi-Agent Systems (MAS) are increasingly employed in applications dealing with safety and information critical tasks (e.g., in eHealth, financial, and energy domains). Therefore, transparency and the trustworthiness of the agents and their behaviors must be enforced. For example, employing reputation based mechanisms can promote the development of trust. Nevertheless, besides recent early stage studies, the existing methods and systems are still unable to guarantee the desired accountability and transparency adequately. In line with the recent trends, we advocate that combining blockchain technology (BCT) and MAS can achieve the distribution of the trust, removing the need for trusted third parties (TTP), potential single points of failure. This paper elaborates on the notions of trust, BCT, MAS, and their integration. Furthermore, to attain a trusted environment, this manuscript details the design and implementation of a system reconciling MAS (based on the Java Agent DEvelopment Framework (JADE)) and BTC (based on Hyperledger Fabric). In particular, the agents’ interactions, computation, tracking the reputation, and possible policies for disagreement-management are implemented via smart contracts and stored on an immutable distributed ledger. The results obtained by the presented system and similar solutions are also discussed. Finally, ethical implications (i.e., opportunities and challenges) are elaborated before concluding the paper.