Video denoising is an elementary but critical task in computer vision and has been widely studied in recent years. However, the existing denoising methods have inevitable drawbacks: some need to predefine rank, some ignore the local information, and most cannot deal with higher-order data. To overcome these shortcomings, we consider two high-order tensor low-rank approximation methods, aiming to achieve color video denoising in a mixed noise environment. First, we establish a high-order tensor framework. Based on this framework, high-order tensor robust principal component analysis (HRPCA) is proposed. Although HRPCA is capable of processing high-order data, there is still a loss of recovery details. Then, we develop another method called high-order tensor low-rank approximation with total variation regularization (HTV). In particular, the TV consists of frontal total variation (FTV) and global total variation (GTV), thus extending the HTV into HFTV and HGTV, respectively. Extensive experimental results of color videos show that the HRPCA and HTV are more efficient in dealing with denoising problems than other state-of-the-art methods.