Pen pal programs for connecting students from around the world through letter writing have been popular for generations. However, traditional technologies have several limitations in supporting pen pal activities. In this study, we explored the potential of video-based asynchronous messaging in supporting the development of children’s cross-cultural friendships. This paper presents the results of a 2-month study of 30 children from the USA and Greece, exploring their uses of, and experiences with, email and an asynchronous video-based messaging tool we developed called VideoPal. The results from this work highlight the important benefits video provides compared to its text counterpart – email. We conclude with a discussion of the key factors that video enables to benefit the development of children’s long-distance friendships.