Systems and methods provide a video messaging service for transmitting video messages between network terminals over a network. After a caller's video-messaging terminal receives a notification that a receiver failed to respond to a communication request, the caller's video-messaging terminal may enable the caller to record a video message and store it for viewing on-demand by a receiver's video-messaging terminal. After recording, the caller's video-messaging terminal transmits a stored message notification terminal to a network server which, in turn, transmits a stored message notification, including an identifier of the caller's video-messaging terminal, to the receiver. Based on the identifier, the receiver's video-messaging terminal may request access to the video message from the callers video-messaging terminal. In response to the request, the caller's video-messaging terminal retrieves the video message from storage and provides it to the receiver's video-messaging terminal over the network.