Dining experience is a crucial element in international tourism because it can encourage tourists to understand local culture and has the potential to increase repeat visitation. A better understanding of tourists' dining choice behaviors is important for destination development; however, the literature has not yet fully investigated this topic, and in particular it is unclear how their behaviors change across repeat visits. This study aimed to fill these gaps by conducting semistructured in-depth interviews with young Australian tourists traveling to Japan. The analysis of the qualitative data identified four major dining choice patterns: perusing the area, searching online sources, hearing from friends or family members, and calling on previous experience. Within the four patterns, perusing the area (i.e., walking around a food district) was the most observed behavior for both first-time and repeat tourists. In addition, repeat tourists tended to choose more local and authentic food due to their motivational development from new-and-touristy to local-and-authentic dining experiences. This study's findings extend the current understanding of tourists' dining choices in the tourism literature and offer suggestions for practitioners.