We present the analytical formulation and the finite element solution of a fractional-order nonlocal continuum model of a Euler-Bernoulli beam. Employing consistent definitions for the fractional-order kinematic relations, the governing equations and the associated boundary conditions are derived based on variational principles. Remarkably, the fractional-order nonlocal model gives rise to a self-adjoint and positive-definite system accepting a unique solution. Further, owing to the difficulty in obtaining analytical solutions to this boundary value problem, a finite element model for the fractional-order governing equations is presented. Following a thorough validation with benchmark problems, the fractional finite element model (f-FEM) is used to study the nonlocal response of a Euler-Bernoulli beam subjected to various loading and boundary conditions. The fractional-order positive definite system will be used here to address some paradoxical results obtained for nonlocal beams through classical integral approaches to nonlocal elasticity. Although presented in the context of a 1D Euler-Bernoulli beam, the f-FEM formulation is very general and could be extended to the solution of any general fractional-order boundary value problem. © 2020 Elsevier Ltd