In this paper, we state and prove a new formula expressing explicitly the integratives of Bernstein polynomials (or B-polynomials) of any degree and for any fractional-order in terms of B-polynomials themselves. We derive the transformation matrices that map the Bernstein and Legendre forms of a degree-n polynomial on [0,1] into each other. By using their transformation matrices, we derive the operational matrices of integration and product of the Bernstein polynomials. These matrices together with the Tau method are then utilized to reduce the solution of this problem to the solution of a system of algebraic equations. The method is applied to solve linear and nonlinear fractional differential equations. Copyright (c) 2013 John Wiley & Sons, Ltd.