An exemplary method includes a video messaging system 1) providing an asynchronous video messaging service, 2) maintaining communication thread data representative of a video communication thread that includes a plurality of video messages exchanged between users of the asynchronous video messaging service, 3) providing a user interface configured to facilitate user interaction with the video communication thread, 4) receiving, by way of the user interface, a user input command to process multiple video messages included in the video communication thread, and 5) stitching together the multiple video messages for use in processing the multiple video messages in response to the user input command. Corresponding systems and methods are also disclosed.