An Australian longitudinal study of 319 Kindergartners developed, implemented and evaluated an intervention, the Pattern and Structure Mathematics Awareness Program (PASMAP). It comprised of repetitions and growing patterns, structured counting and grouping, grids and shapes, partitioning, additive and multiplicative structures, measurement and data, and transformations. Each component was implemented, evaluated and refined as a cyclic process in collaboration with co-operating teachers, replacing and extending the regular mathematics program. An innovative pedagogical approach was effective in engaging students in modelling and representing, visualising and generalising, and sustaining their learning. On an interview-based measure of mathematics achievement pre- and post-intervention, there were significant differences found between the intervention and comparison groups at the end of the intervention year (p < 0.026) and highly significant differences found at the follow-up assessment (p < 0.002) ten months later. A descriptive analysis showed students' progress through five levels of structural development where most students advanced through one or more levels as they progressed through the program. The upper third of students demonstrated emergent generalisations at the structural and advanced structural level which supported early algebraic thinking. Less-able students also showed impressive growth--half of these students moved from pre-structural to at least emergent level over the duration of the program. Students' growth in structural development is exemplified at five points during the intervention through fine-grained analyses of mathematical representations and explanations. The study demonstrates that Kindergartners are capable of developing mathematical patterns and structural relationships well beyond curriculum expectations.