In modern cities, complaining has become an important way for citizens to report emerging urban issues to governments for quick response. For ease of retrieval and handling, government officials usually organize citizen complaints by manually assigning tags to them, which is inefficient and cannot always guarantee the quality of assigned tags. This work attempts to solve this problem by recommending tags for citizen complaints. Although there exist many studies on tag recommendation for textual content, few of them consider two characteristics of citizen complaints, i.e., the spatio-temporal correlations and the taxonomy of candidate tags. In this paper, we propose a novel Spatio-Temporal Taxonomy-Aware Recommendation model (STAR), to recommend tags for citizen complaints by jointly incorporating spatio-temporal information of complaints and the taxonomy of candidate tags. Specifically, STAR first exploits two parallel channels to learn representations for textual and spatio-temporal information. To effectively leverage the taxonomy of tags, we design chained neural networks that gradually refine the representations and perform hierarchical recommendation under a novel taxonomy constraint. A fusion module is further proposed to adaptively integrate contributions of textual and spatio-temporal information in a tag-specific manner. We conduct extensive experiments on a real-world dataset and demonstrate that STAR significantly performs better than state-of-the-art methods. The effectiveness of key components in our model is also verified through ablation studies.