The key purpose of the present work is to introduce a numerical algorithm for the solution of the fractional Klein-Gordon equation (FKGE). The numerical algorithm is based on the applications of the operational matrices of the Legendre scaling functions. The main advantage of the numerical algorithm is that it reduces the FKGE into Sylvester form of algebraic equations which significantly simplify the problem. Numerical results derived by using suggested numerical scheme are compared with the exact solution. The results show that the suggested algorithm is very user friendly for solving FKGE and accurate.