This paper is concerned with deriving an operational matrix of fractional-order derivative of Fibonacci polynomials. As an application of this matrix, a spectral algorithm for solving some fractional-order initial value problems is exhibited and implemented. The properties of Fibonacci polynomials are presented. The operational matrix of fractional derivative is achieved. This matrix and collocation method are utilized to reduce the solution of the fractional delay differential equations to a system of algebraic equations which can be solved by using Newton's iterative method. Illustrative examples are included to demonstrate the validity and applicability of the technique