The structural information is critical in image analysis as one of the most popular topics in the computational intelligence area. To capture the structural information of the given images, the nuclear-norm matrix regression (NMR) framework provides a natural way by successfully formulating the two-dimensional image error matrix into the image analysis. Nevertheless, although NMR shows its powerful performance in robust face recognition, its intrinsic regression/classification mechanism is still unclear, which restricts its capability. Furthermore, since NMR works in a sample-dependent scheme, it requires remodelling for each given image sample and leads to a failure in learning the intrinsic and structural information from the given image samples. Leveraging the superiority and drawbacks of the NMR framework, in this paper, we propose Probabilistic Nuclear-norm Matrix Regression (PNMR). We form the idea of PNMR with theoretical deduction using Bayesian inference to clearly show its probability interpretation, where we present a unified as well as a delicated formulation for optimization. PNMR can be proven to achieve the joint learning of the NMR-style formulation regularized by the $L_{2,1}$-norm, making it adaptive to arbitrary given image samples. To fully consider the intrinsic relationships of the observed samples, we propose the Probabilistic Nuclear-norm Matrix Regression regularized by Random Graph (PNMR-RG) on the basis of PNMR. Extensive experiments on several image datasets were performed and comparisons were made with 10 state-of-the-art methods to demonstrate the feasibility and promising performance of both PNMR and PNMR-RG.