An integer-valued polynomial is a polynomial with rational coefficients that takes an integer value when evaluated at an integer. The binomial polynomials form a regular basis for the Z-module of all integer-valued polynomials. Using the idea of a p-ordering and a p-sequence, Bhargava describes a similar characterization for polynomials that are integer-valued on some subset of the integers. This thesis focuses on characterizing the polynomials that are integer-valued on the Fibonacci numbers. For a certain class of primes p, we give a formula for the p-sequence of the Fibonacci numbers and an algorithm for finding a p-ordering using Coelho and Parry’s results on the distribution of the Fibonacci numbers modulo powers of primes. Knowing the p-sequence, we can then find a p-local regular basis for the polynomials that are integer-valued on the Fibonacci numbers using Bhargava’s methods. A regular basis can be constructed from p-local bases for all primes p.