Orthogonal moments are used to represent digital images with minimum redundancy. Orthogonal moments with fractional-orders show better capabilities in digital image analysis than integer-order moments. In this work, the authors present new fractional-order shifted Gegenbauer polynomials. These new polynomials are used to define a novel set of orthogonal fractional-order shifted Gegenbauer moments (FrSGMs). The proposed method is applied in gray-scale image analysis and recognition. The invariances to rotation, scaling and translation (RST), are achieved using invariant fractional-order geometric moments. Experiments are conducted to evaluate the proposed FrSGMs and compare with the classical orthogonal integer-order Gegenbauer moments (GMs) and the existing orthogonal fractional-order moments. The new FrSGMs outperformed GMs and the existing orthogonal fractional-order moments in terms of image recognition and reconstruction, RST invariance, and robustness to noise.