A video communication system that replaces actual live images of the participating users with animated avatars. A method may include initiating communication between a first user device and a remote user device; receiving selection of a new avatar to represent a user of the first user device; identifying a new avatar file for the new avatar in an avatar database associated with the first user device; determining that the new avatar file is not present in a remote avatar database associated with the remote user device; and transmitting the new avatar file to the remote avatar database in response to determining that the new avatar file is not present in the remote avatar database.