The embedding layers transforming input words into real vectors are the keycomponents of deep neural networks used in natural language processing.However, when the vocabulary is large (e.g., 800k unique words in theOne-Billion-Word dataset), the corresponding weight matrices can be enormous,which precludes their deployment in a limited resource setting. We introduce anovel way of parametrizing embedding layers based on the Tensor Train (TT)decomposition, which allows compressing the model significantly at the cost ofa negligible drop or even a slight gain in performance. Importantly, our methoddoes not take the pre-trained model and compress its weights but rathersupplants the standard embedding layers with their TT-based counterparts. Theresulting model is then trained end-to-end, however, it can capitalize onlarger batches due to the reduced memory requirements. We evaluate our methodon a wide range of benchmarks in sentiment analysis, neural machinetranslation, and language modeling, and analyze the trade-off betweenperformance and compression ratios for a wide range of architectures, from MLPsto LSTMs and Transformers.