Machine learning accelerators such as the Tensor Processing Unit (TPU) are already being deployed in the hybrid cloud, and we foresee such accelerators proliferating in the future. In such scenarios, secure access to the acceleration service and trustworthiness of the underlying accelerators become a concern. In this work, we present AccShield, a new method to extend trusted execution environments (TEEs) to cloud accelerators which takes both isolation and multi-tenancy into security consideration. We demonstrate the feasibility of accelerator TEEs by a proof of concept on an FPGA board. Experiments with our prototype implementation also provide concrete results and insights for different design choices related to link encryption, isolation using partitioning and memory encryption.