Methods and apparatus are provided for automatically transcoding media files. An exemplary method comprises obtaining an input media file having an input file format and encoded with a codec of a first type; automatically determining output media file formats for transcoding the input media file based on statistics of previously transcoded files and statistics of trending media formats for previously downloaded files; and transcoding the input media file into transcoded output media files using a codec of a second type to obtain the determined output media file formats. The output media file formats can be automatically determined using a weighting scheme. Transcoding algorithms are optionally automatically selected based on transcoding algorithms previously used to transcode proximally similar files as the input media file. Input files can be dynamically prioritized for transcoding based on a complexity rating of the determined output media file formats and a ranking of selected transcoding algorithms Metadata is optionally generated for transcoded output media files and stored in the transcoded output media files and/or a separate media catalogue.