The tensor tubal rank, defined based on the tensor singular value decomposition (t-SVD), has obtained promising results in hyperspectral image (HSI) denoising. However, the framework of the t-SVD lacks flexibility for handling different correlations along different modes of HSIs, leading to suboptimal denoising performance. This project mainly makes three contributions. First, we introduce a new tensor rank named tensor fibered rank by generalizing the t-SVD to the mode-k t-SVD, to achieve a more flexible and accurate HSI characterization. Since directly minimizing the fibered rank is NP-hard, we suggest a three-directional tensor nuclear norm (3DTNN) and a three-directional log based tensor nuclear norm (3DLogTNN) as its convex and non-convex relaxation to provide an efficient numerical solution, respectively. Second, we propose a fibered rank minimization model for HSI mixed noise removal, in which the underlying HSI is modeled as a low-fibered-rank component. Third, we develop an efficient alternating direction method of multipliers (ADMMs) based algorithm to solve the proposed model, especially, each sub problem within ADMM is proven to have a closed-form solution, although 3DLogTNN is non-convex. Extensive experimental results demonstrate that the proposed method has superior denoising performance, as compared with the state of the art competing methods on low-rank matrix/tensor approximation and noise modeling. This project is implemented with MATLAB software.