The main purpose of this paper is to define the Appell-Fibonacci polynomials by associating the Appell polynomials, an important concept in mathematics, with Fibonomial coefficients. In this study, various properties and recurrence relations of the Appell-Fibonacci polynomials were established, and a determinantal definition is provided. Additionally, the Appell-Fibonacci polynomial matrix is defined, and its relationship with the generalized Fibo-Pascal matrix is presented. Lastly, the generating function for Appell-Fibonacci polynomials is extended to bilinear and bilateral functions and showcasing several special results.