We introduce an optomechanical scheme for the probabilistic preparation of single-phonon Fock states of mechanical modes based on photo-subtraction. The quality of the produced mechanical state is confirmed by a number of indicators, including phonon statistics and conditional fidelity. We assess the detrimental effect of parameters such as the temperature of the mechanical system and address the feasibility of the scheme with state-of-the-art technology.