Network representation learning (NRL) aims at modeling network graph by encoding vertices and edges into a low-dimensional space. These learned representations can be used for subsequent applications, such as vertex classification and link prediction. Negative Sampling (NS) is the most widely used method for boosting the performance of NRL. However, most of the existing work only randomly draws negative samples based on vertex frequencies, i.e., the vertices with higher frequency are more likely to be drawn, which ignores the situation that the sampled one may not be a true negative sample, thus, lead to undesirable embeddings. In this paper, we propose a new negative sampling method, called Hierarchical Negative Sampling (HNS), which is able to model the latent structures of vertices and learn the relations among them. During sampling, HNS can draw more appropriate negative samples and thereby obtain better performance on network embeddings. Firstly, we theoretically demonstrate the superiority of HNS over NS. And then we use experimental results to show that our proposed method outperforms the state-of-the-art models on vertex classification tasks at different training scales in real-world networks.