A system for supporting a video message service and method thereof is disclosed, a system for supporting a video message service comprises a video message center for when a calling-party mobile terminal is connected via a video call, creating a video message having a preset size based on video data received via the video call according to the reception authentication information of a called-party mobile terminal, and transmitting the created video message using a preset transmission method according to the reception state of the called-party mobile terminal and an authentication server for performing an authentication procedure on the called-party mobile terminal so as to transmit the video message, and provides reception authentication information, based on the results of the authentication procedure, to the video message center.