In Russian negative sentences the verb's direct object may appear either in the accusative case, which is licensed by the verb (as is common cross-linguistically), or in the genitive case, which is licensed by the negation (Russian-specific "genitive-of-negation" phenomenon). Such sentences were used to investigate whether case marking is employed for anticipating syntactic structure, and whether lexical heads other than the verb can be predicted on the basis of a case-marked noun phrase. Experiment 1, a completion task, confirmed that genitive-of-negation is part of Russian speakers' active grammatical repertoire. In Experiments 2 and 3, the genitive/accusative case manipulation on the preverbal object led to shorter reading times at the negation and verb in the genitive versus accusative condition. Furthermore, Experiment 3 manipulated linear order of the direct object and the negated verb in order to distinguish whether the abovementioned facilitatory effect was predictive or integrative in nature, and concluded that the parser actively predicts a verb and (otherwise optional) negation on the basis of a preceding genitive-marked object. Similarly to a head-final language, case-marking information on preverbal noun phrases (NPs) is used by the parser to enable incremental structure building in a free-word-order language such as Russian.