Web search queries have been observed to exhibit properties of a rudimentary language system, distinct from the mother language from which words of the queries are drawn. It has been hypothesized that the language of search queries is fast growing in complexity, reflected in the steady increase of query lengths over the years. In this research, we make the first attempts to quantify change in the linguistic structure of search queries by examining large query logs spaced four years apart. We adopt a multi-pronged approach and analyze query structure from three different perspectives, namely, language models, complex networks and positional preferences of words. All experimental findings confirm that the linguistic structure of Web search queries is indeed evolving.