Masonry vaulted structures constitute a large proportion of the historical buildings in the Eastern and Western world. Due to the high complexity of their geometric features, a full 3D analysis cannot be avoided for a comprehensive understanding of their structural performance. In recent numerical studies, limit analysis could be a promising alternative to rapidly analyse the collapse behaviour of the masonry system, instead of performing a time-consuming finite element analysis. However, the element deformability is usually not fully taken into account in most of those 3D implementations, considering the underlying explosion of problem size. This contribution proposes a deformable tetrahedron element for the limit analysis of masonry vaulted structures. The element strain rate is assumed to be homogeneous with rigid-plastic behaviour, and the velocity discontinuities across the element boundaries are included. The Drucker-Prager yield criterion is adopted to model the element plasticity, with an application of the classic cohesive-frictional model at interfaces. Both flow rules for the elements and interfaces are associated. The limit analysis formulations will be stated from a kinematic perspective, formalised as a standard Second-Order Cone Programming (SOCP). The collapse of a cross-ribbed vault is investigated as an implementation of this approach, and the results indicate the reliability of the proposed approach. The load prediction from our approach is more conservative than the counterpart analysis using infinite resistant blocks and is more consistent with the experimental results, to some extent demonstrating the necessity of considering the element deformability when modelling the masonry vault structures.