In this study, we investigated the interaction between givenness and complexity on the choice of syntactic structure, via two experiments using speeded acceptability judgments. Experiment 1 showed that for the Danish dative alternation, given–new orders are only easier to process for double-object or NP constructions, whereas PP constructions are unaffected. This replicates previous findings for the English dative alternation. Experiment 2 revealed that when a long NP precedes a short NP—a suboptimal complexity relation—the effect of givenness is neutralized, whereas givenness remains influential when the complexity relation between the NPs in the sentence is optimal. This is consistent with the view that in online parsing, the actual syntactic structure-building process is primary, whereas any higher-order computations such as discourse linking are secondary. The relative complexity of the NPs in the double-object construction directly affects the structure-building process, whereas the decoding of the discourse structure is a later and less crucial phenomenon, resulting in neutralization of the givenness effect in cases in which the complexity relation is suboptimal.