Deep Neural Networks (DNNs) trained on proprietary company data offer a competitive edge for the owning entity. However, these models can be attractive to competitors (or malicious entities), who can copy or clone these proprietary DNN models to use them to their advantage. Since these attacks are hard to prevent, it becomes imperative to have mechanisms in place that enable an affected entity to verify the ownership of its DNN models with very high confidence. Watermarking of deep neural networks has gained significant traction in recent years, with numerous (watermarking) strategies being proposed as mechanisms that can help verify the ownership of a DNN in scenarios where these models are obtained without the owner’s permission. However, a growing body of work has demonstrated that existing watermarking mechanisms are highly susceptible to removal techniques, such as fine-tuning, parameter pruning, or shuffling. In this paper, we build upon extensive prior work on covert (military) communication and propose TATTOOED, a novel DNN watermarking technique that is robust to existing threats. We demonstrate that using TATTOOED as their watermarking mechanism, the DNN owner can successfully obtain the watermark and verify model ownership even in scenarios where 99% of model parameters are altered. Furthermore, we show that TATTOOED is easy to employ in training pipelines and has negligible impact on model performance.