The relation between prosody and syntax is investigated here by tracing the emergence of each in a new language, Al-Sayyid Bedouin Sign Language. We analyze the structure of narratives of four signers of this language: two older second generation signers, and two about 15 years younger. We find that younger signers produce prosodic cues to dependency between semantically related constituents, e.g., the two clauses of conditionals, revealing a type and degree of complexity in their language that is not frequent in that of the older pair. In these younger signers, several rhythmic and (facial) intonational cues are aligned at constituent boundaries, indicating the emergence of a grammatical system. There are no overt syntactic markers (such as complementizers) to relate clauses; prosody is the only clue. But this prosodic complexity is matched by syntactic complexity inside propositions in the younger signers, who are more likely to use pronouns as abstract grammatical markers of arguments, and to combine predicates with their arguments within in a constituent. As the prosodic means emerge for identifying constituent types and signaling dependency relations between them, the constituents themselves become increasingly complex. Finally, our study shows that the emergence of grammatical complexity is gradual.