Agri-food waste is generated at various food cycle stages and is considered to be a valuable feedstock in energy systems and chemical syntheses. This research identifies the potential and suitability of a representative agri-food waste sample (i.e., plum stones) as a solid fuel. Ground plum stones containing 10, 15, and 20 wt.% of rye bran were subjected to pelletization. The pelletizer was operated at 170, 220, and 270 rpm, and its power demand for the mixture containing 20 wt.% of rye bran was 1.81, 1.89, and 2.21 kW, respectively. Such pellets had the highest quality in terms of their density (814.6 kg·m−3), kinetic durability (87.8%), lower heating value (20.04 MJ·kg−1), and elemental composition (C: 54.1 wt.%; H: 6.4 wt.%; N: 0.73 wt.%; S: 0.103 wt.%; Cl: 0.002 wt.%; O: 38.2 wt.%). Whole plum stones and pellets were subjected to combustion in a 25 kW retort grate boiler in order to determine the changes in the concentrations of NO, SO2, CO, CO2, HCl, and O2 in the post-combustion flue gas. Collected results indicate that plum stone−rye bran pellets can serve as effective substitutes for wood pellets in prosumer installations, meeting the Ecodesign Directive requirements for CO and NO.