Heterogeneous silica supported rhodium-phosphine complex catalysts are employed for the first time in the catalytic decarbonylation of aldehydes in continuous gas-phase. The reaction protocol is exemplified for the decarbonylation of p-tolualdehyde to toluene and further extended to other aromatic and aliphatic aldehydes achieving excellent results in terms of both conversion and selectivity.