We present a novel probabilistic finite element method (FEM) for the solution and uncertainty quantification of elliptic partial differential equations based on random meshes, which we call random mesh FEM (RM-FEM). Our methodology allows to introduce a probability measure on classical FEMs to quantify the uncertainty due to numerical errors either in the context of a-posteriori error quantification or for FE based Bayesian inverse problems. The new approach involves only a perturbation of the mesh and an interpolation that are very simple to implement We present a posteriori error estimators and a rigorous a posteriori error analysis based uniquely on probabilistic information for standard piecewise linear FEM. A series of numerical experiments illustrates the potential of the RM-FEM for error estimation and validates our analysis. We furthermore demonstrate how employing the RM-FEM enhances the quality of the solution of Bayesian inverse problems, thus allowing a better quantification of numerical errors in pipelines of computations. (C) 2021 Elsevier B.V. All rights reserved.