In this paper, the optimized decomposition method, which was developed to solve integer-order differential equations, will be modified and extended to handle nonlinear fractional differential equations. Fractional derivatives will be considered in terms of Caputo sense. The suggested modifications design new optimized decompositions for the series solutions depending on linear approximations of the nonlinear equations. Two optimized decomposition algorithms have been introduced to obtain approximate solutions of broad classes of IVPs consisting of nonlinear fractional ODEs and PDEs. A comparative study was conducted between the proposed algorithms and the Adomian decomposition method by means of some test illustration problems. The implemented numerical simulation results showed that the proposed algorithms give better accuracy and convergence, and reduce the complexity of computational work compared to the Adomian's approach. This confirms the belief that the optimized decomposition method will be used effectively and widely as a powerful tool in solving various fractional differential equations.