This article is based on a research project focusing on Norwegian teachers' planning and documentation of children's learning in preschool. Norwegian preschools follow a national curriculum and teachers are obliged to document both professional practice and learning outcomes. The aim of the article is to investigate teachers' experiences of challenges, problems and dilemmas related to their planning and documentation. Questions asked are: "How do teachers plan their work with the children?", "What is the focus in documentation?", and "How do teachers express relationships between planning and documentation?" Findings reveal that there are specific problems and dilemmas connected to relationships between teachers' planning, documentation, and reflection on children's learning in preschool. The results are described in relation to each of the research questions.