This study presents a framework to perform stability analysis of nonlocal solids whose behavior is described according to the fractional-order continuum theory. In this formulation, space fractional-order operators are used to capture the nonlocal response of the medium by means of nonlocal kinematic relations. We use the geometrically nonlinear fractional-order kinematic relations within an energy based approach to establish the Lagrange-Dirichlet stability criteria for nonlocal structures. This energy based approach to nonlocal structural stability is possible due to a positive-definite and thermodynamically consistent definition of the deformation energy enabled by the fractional-order kinematic formulation. The Rayleigh-Ritz coefficient for critical load is also derived for linear buckling conditions. The fractional-order formulation is finally used to determine critical loads for buckling of the slender nonlocal beams and plates using a dedicated fractional-order finite element solver. Results establish that, in contrast to existing studies, the effect of nonlocal interactions is observed on both the material and the geometric stiffness, when using the fractional-order kinematics approach. These observations are supported quantitatively via the solution of case studies that focus on the critical buckling response of fractional-order nonlocal slender structures, and a direct comparison of the fractional-order approach with classical nonlocal approaches. © 2021 Elsevier Ltd