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 of the suggested algorithms with the Adomian decomposition method was performed by means of some test illustration problems. The executed numerical simulation results demonstrated that the proposed algorithms give better accuracy and convergence compared with Adomian's approach. This confirms the belief that the optimized decomposition method will be effectively and widely used in solving various functional equations.