The para-terphenyl derivative vialinin A (Vi-A), isolated from Thelephora fungi, has been characterized as a potent inhibitor of the ubiquitin-specific protease 4 (USP4). Blockade of USP4 contributes to the anti-inflammatory and anticancer properties of the natural product. We have investigated the interaction of Vi-A with USP4 by molecular modeling, to locate the binding site (around residue V98 within the domain in USP segment) and to identify the binding process and interaction contacts. From this model, a series of 32 p-terphenyl compounds were tested as potential USP4 binders, mainly in the vialinin, terrestrin and telephantin series. We identified 11 compounds presenting a satisfactory USP4 binding capacity, including two fungal products, vialinin B and aurantiotinin A, with a more favorable empirical energy of USP4 interaction (ΔE) than the reference product Vi-A. The rare p-terphenyl aurantiotinin A, isolated from the basidiomycete T. aurantiotincta, emerged as a remarkable USP4 binder. Structure-binding relationships have been identified and discussed, to guide the future design of USP4 inhibitors based on the p-terphenyl skeleton. The docking study should help the identification of other protease inhibitors from fungus.