Male pufferfish (Torquigener albomaculosus) construct “mystery circles”, geometric circular structures with radially aligned peaks and valleys, on sandy seabeds for reproduction. We discovered an earliest-stage mystery circle composed of dozens of irregular depressions. The structure changed to a primitive circular form with radially aligned valleys and a circular depression in the central area on day 2. The number of valleys increased, and the radius of the structure was much smaller than that of the final structure. These features were observed from days 2 to 4, considered the early stage of construction. The mystery circle had radially aligned peaks and valleys with a central flat area, while the radius and the differences in elevation between the peaks and valleys were increasing. These features, which were observed from days 5 to 8, were considered the middle stage of construction. On day 9, the mystery circle was completed. An irregular pattern was formed in the central area, and the radially aligned peaks were decorated with shell and coral fragments. These are the first recorded observations of construction of a mystery circle from the earliest stage.