Cohomological techniques within the Batalin-Vilkovisky (BV) extension of the Becchi-Rouet-Stora-Tyutin (BRST) formalism have proved invaluable for classifying consistent deformations of gauge theories. In this work we investigate the application of this idea to massive field theories in the Stueckelberg formulation. Starting with a collection of free massive vectors, we show that the cohomological method reproduces the cubic and quartic vertices of massive Yang-Mills theory. In the same way, taking a Fierz-Pauli graviton on a maximally symmetric space as the starting point, we are able to recover the consistent cubic vertices of nonlinear massive gravity. The formalism further sheds light on the characterization of Stueckelberg gauge theories, by demonstrating for instance that the gauge algebra of such models is necessarily Abelian and that they admit a Born-Infeld-like formulation in which the action is simply a combination of the gauge-invariant structures of the free theory.