I was wondering about the dinosaurs and prehistoric animals; how all of this was part of the creation and if they were part of the plan or creation. Was there millions of years between them and the first people?

Dinosaurs and other extinct animals can easily fit into a recent creation framework. The book of Job is certainly one of the earliest books of the Bible to be written down. In this book, two creatures are mentioned that could easily be so-called prehistoric animals. Behemoth (Job 40:15-24 [15] Behold now behemoth, which I made with thee; he eateth grass as an ox. [16] Lo now, his strength is in his loins, and his force is in the navel of his belly. [17] He moveth his tail like a cedar: the sinews of his stones are wrapped together. [18] His bones are as strong pieces of brass; his bones are like bars of iron. [19] He is the chief of the ways of God: he that made him can make his sword to approach unto him. [20] Surely the mountains bring him forth food, where all the beasts of the field play. [21] He lieth under the shady trees, in the covert of the reed, and fens. [22] The shady trees cover him with their shadow; the willows of the brook compass him about. [23] Behold, he drinketh up a river, and hasteth not: he trusteth that he can draw up Jordan into his mouth. [24] He taketh it with his eyes: his nose pierceth through snares.
See All...) is often identified with the elephant by Bible scholars. However, that will only work if we do not believe the text to be accurate. He moves his tail like a cedar tree (Job 40:17He moveth his tail like a cedar: the sinews of his stones are wrapped together.
See All...). This indicates a massive tail, not the small tail of an elephant. There are other reasons as well. The description sounds more like one of the dinosaurs than anything else.

Then there is leviathan (Job 41:1-34 [1] Canst thou draw out leviathan with an hook? or his tongue with a cord which thou lettest down? [2] Canst thou put an hook into his nose? or bore his jaw through with a thorn? [3] Will he make many supplications unto thee? will he speak soft words unto thee? [4] Will he make a covenant with thee? wilt thou take him for a servant for ever? [5] Wilt thou play with him as with a bird? or wilt thou bind him for thy maidens? [6] Shall the companions make a banquet of him? shall they part him among the merchants? [7] Canst thou fill his skin with barbed irons? or his head with fish spears? [8] Lay thine hand upon him, remember the battle, do no more. [9] Behold, the hope of him is in vain: shall not one be cast down even at the sight of him? [10] None is so fierce that dare stir him up: who then is able to stand before me? [11] Who hath prevented me, that I should repay him? whatsoever is under the whole heaven is mine. [12] I will not conceal his parts, nor his power, nor his comely proportion. [13] Who can discover the face of his garment? or who can come to him with his double bridle? [14] Who can open the doors of his face? his teeth are terrible round about. [15] His scales are his pride, shut up together as with a close seal. [16] One is so near to another, that no air can come between them. [17] They are joined one to another, they stick together, that they cannot be sundered. [18] By his neesings a light doth shine, and his eyes are like the eyelids of the morning. [19] Out of his mouth go burning lamps, and sparks of fire leap out. [20] Out of his nostrils goeth smoke, as out of a seething pot or caldron. [21] His breath kindleth coals, and a flame goeth out of his mouth. [22] In his neck remaineth strength, and sorrow is turned into joy before him. [23] The flakes of his flesh are joined together: they are firm in themselves; they cannot be moved. [24] His heart is as firm as a stone; yea, as hard as a piece of the nether millstone. [25] When he raiseth up himself, the mighty are afraid: by reason of breakings they purify themselves. [26] The sword of him that layeth at him cannot hold: the spear, the dart, nor the habergeon. [27] He esteemeth iron as straw, and brass as rotten wood. [28] The arrow cannot make him flee: slingstones are turned with him into stubble. [29] Darts are counted as stubble: he laugheth at the shaking of a spear. [30] Sharp stones are under him: he spreadeth sharp pointed things upon the mire. [31] He maketh the deep to boil like a pot: he maketh the sea like a pot of ointment. [32] He maketh a path to shine after him; one would think the deep to be hoary. [33] Upon earth there is not his like, who is made without fear. [34] He beholdeth all high things: he is a king over all the children of pride.
See All...). Leviathan is a type of the devil (Isaiah 27:1In that day the LORD with his sore and great and strong sword shall punish leviathan the piercing serpent, even leviathan that crooked serpent; and he shall slay the dragon that is in the sea.
See All...), but God describes him to Job as a living sea creature. And what a creature he is! No man can catch him. He breathes fire out of his mouth. He cannot be turned to flight by spears or arrows. The description is of a creature like none known to exist today.

There is no reason to doubt that these animals existed in the time of Adam and beyond. They may have even been on Noah's ark--probably as young (and much smaller) animals. However, it is likely that the change in climate that occurred after the flood made it difficult for them to survive and they were soon extinct. Dinosaur prints have been found alongside of human footprints in some places, so it is probable that they existed at the same time.

Since I do not have absolute statements from the Bible, I cannot say that this is the only possible solution. However, according to what information the Bible gives us, I believe that this is the most likely solution.