In this paper we address the problem of accurately and efficiently cross-referencing text fragments with Wikipedia pages, in a way that structured knowledge is provided about the (unstructured) input text by resolving synonymy and polysemy. We take inspiration from the invited talk of Chakrabarti at WSDM 2010, and extend his proposed scenario from the annotation of entire documents to the annotation of short texts, such as snippets of search-engine results, tweets, news, etc.. These short and poorly composed texts pose new challenges in terms of efficiency and effectiveness of the annotation process, that we address by proposing TAGME, the first system that performs an accurate and on-the-fly annotation of these short textual fragments. A large set of experiments shows that TAGME significantly outperforms state-of-the-art algorithms [Milne and Witten 2008, Chakrabarty et al. 2009] when they are adapted to work on short texts, and surprisingly, it results competitive (if not superior!) on long texts with the plus of being faster.