Multi-turn tool calling is essential for LLMs to function as autonomous agents, yet synthesizing the training data required for these capabilities remains a fundamental challenge. Existing synthetic data generation pipelines often produce unrealistic dialogues for two reasons: they chain tools that are only superficially compatible rather than aligned with meaningful user tasks, and they generate dialogues in one shot, which often introduces arguments that were neither provided by the user nor produced by prior tool calls. These issues also lead to a severe underrepresentation of multi-step tool interactions. We introduce ToolWeave, a structured framework for synthesizing realistic multi-turn tool-calling dialogues. ToolWeave supports realistic multi-step workflows (or tool sequences) by constructing tools with built-in dependencies and filtering candidate workflows based on their alignment with user goals. It reduces parameter hallucinations through a fine-grained planning stage that explicitly tracks parameter provenance. As a result, 44.87% of conversational turns in ToolWeave-generated data are multi-step, and the data contains fewer hallucinations in parameters and tool names. Consequently, LLMs fine-tuned on ToolWeave consistently outperform those fine-tuned on prior datasets across three public benchmarks. Notably, Llama-3.1-70B fine-tuned on ToolWeave achieves 39.75% on BFCL-V3, compared to 23.50% when fine-tuned on SOTA ToolFlow data.