Public Key Searchable Encryption (PKSE) has essential applications in cloud storage because it allows users to search over encrypted data. To identify illegal users, many traceable PKSE schemes have been proposed. However, existing schemes cannot trace the keywords that illegal users searched and protect users’ privacy simultaneously. It is challenging to bind users’ identities and keywords while protecting their privacy. Moreover existing traceable PKSE schemes do not consider the unforgeability and immutability of trapdoor query records which leads to frame-up and denial. In this paper, to address these problems, we propose a blockchain-based privacy-preserving PKSE with strong traceability (BP3KSEST) scheme. The main features of our scheme are as follows: (1) authorized users can obtain trapdoors from trapdoor generation center without releasing their identities and keywords; (2) When required, a trusted third party (TTP) can trace both illegal users’ identities and the keywords which they searched; (3) trapdoor query records are unforgeable and immutable. This scheme is appropriate for scenarios where privacy must be addressed, e.g, electronic health record (EHR). We formalize the definition and security model of our BP3KSEST scheme. Furthermore, we present a concrete construction and prove its security. Finally, the implementation is conducted to analyze its efficiency.