In multi-agent planning, preserving the agents’ privacy has become an increasingly popular research topic. In multi-agent privacy-preserving planning, agents jointly compute a plan that achieves mutual goals by keeping certain information private to the individual agents. Unfortunately, preserving the privacy of such information can severely restrict the accuracy of the heuristic functions used while searching for solutions. Recently, it has been shown that centralized planning based on Width-based search is a very effective approach over several benchmark domains, even when the search is driven by uninformed heuristics. In this paper, we investigate the usage of Width-based search in the context of (decentralised) multi-agent privacy-preserving planning, addressing the challenges related to the agents’ privacy and performance. An experimental study analyses the effectiveness of our techniques and compares them with the state-of-the-art.