As the Cloud Computing technology becomes mature, the need increases rapidly to store sensitive data securely on the cloud server. Since the cloud is not trusted, the data should be stored in an encrypted form at the server. An inherent problem is how to query the encrypted data efficiently. Recently, some searchable encryption schemes have been proposed in the literatures. Although the existing searchable encryption schemes allow a user to search the encrypted data securely without decrypting it, these solutions cannot support the verifiability of the search results. In this paper, the authors propose a verifiable fuzzy keyword search scheme based on the symbol-tree which not only supports the fuzzy keyword search over encrypted data, but also enjoys the verifiability of the search outcome.