An apparatus and a method for providing a video telephony service in a mobile communication terminal are provided. The apparatus for providing the video telephony service in the mobile communication terminal includes a controlling unit for receiving preferred video format information from a peer mobile communication terminal during a signaling procedure with the peer mobile communication terminal for the video telephony service and for determining a video format to use in the video telephony service using the received preferred video format, and a video codec for encoding and decoding video data that is transmitted to and received from the peer mobile communication terminal, using the determined video format.