Choosing appropriate referring expressions requires assessing whether a referent is "available" to the addressee either perceptually or through discourse. In Study 1, we found that 3- and 4-year-olds, but not 2-year-olds, chose different referring expressions (noun vs. pronoun) depending on whether their addressee could see the intended referent or not. In Study 2, in more neutral discourse contexts than previous studies, we found that 3- and 4-year-olds clearly differed in their use of referring expressions according to whether their addressee had already mentioned a referent. Moreover, 2-year-olds responded with more naming constructions when the referent had not been mentioned previously. This suggests that, despite early social-cognitive developments, (a) it takes time to master the given/new contrast linguistically, and (b) children understand the contrast earlier based on discourse, rather than perceptual context.