Across two studies, we demonstrate that children may be capable of negotiation earlier than previously thought, using a novel paradigm. In Study 1, 3- to 5-year-old children in Australia completed a tower-building task, in which they were given an opportunity to make trading choices that could allow both them and a confederate to succeed. A majority of children across age groups selected the efficient trade option over other alternatives. In Study 2, we modified the task to have less structure. With no pre-set options, 5-year-old children initiated efficient exchange to a greater extent than younger children. A different task that relied on distributing desirable vs. less desirable rewards yielded a complementary pattern. The two studies shed light on the onset and developmental trajectory of children’s capacity to initiate and execute a mutually beneficial deal, varying across different task contexts.