MapStory is an LLM-based animation prototyping tool that leverages a dual-agent LLM architecture to generate editable map animation sequences from natural language text. Based on user-written scripts, it automatically generates a scene decomposition that breaks down text into key map animation primitives, such as camera movements, visual highlights, and animated elements. The system includes a researcher agent that leverages LLM to accurately query geospatial information using web searches, automatically extracting relevant regions, routes, and coordinates, while allowing users to edit and query changes or additional information to improve the results. Users can also fine-tune the parameters of these building blocks through an interactive timeline editor. The system's design and architecture are detailed based on formative interviews with professional animators and an analysis of 200 existing map animation videos. An evaluation, including expert interviews (N=5) and a usability study (N=12), demonstrates that MapStory facilitates user-generated map animations, accelerates iteration, encourages creative exploration, and lowers the barrier to creating map-centric stories.