Han Solo acquired the Millennium Falcon from Lando Calrissian in a high-stakes sabacc game. Some versions of the story note that at the time Lando owned a used starship lot and had specifically bet "any ship on [his] lot". Han cunningly claimed Lando's own heavily souped-up custom job of a YT-1300 which had been carelessly left with the other ships. The Falcon itself was a chop job from the start--having been cobbled together from two scrapped ships in a Nar Shaddaa junkyard. Since it had been pieced back together, more than one previous owner had worked on improving the design to match some vision of perfection. As a result, any given component on the ship was unlikely to be joined to components made by the same manufacturer. Under Han, speed became the ship's raison d'etre. Solo pushed the ship to its limit and beyond, going so far as to equip his ship with specialized devices to streamline it while it was in a tachyonic state.
The Millennium Falcon was first seen on episode IV, as an old Obi-wan and Luke walk into the hanger, followed shortly by a Stormtrooper squad. Going by timeline, you can see the Falcon in episode 3, there is a scene that shows the senate building dotted by spacecraft and you can see the Falcon come in and land(it is the 'Falcon. just under a different name at that time. the name she had then was "stellar envoy". at that point she was a stock light freighter, and hadn't been extensively modified yet. her purpose there was to receive instructions,and a device from a group of Jedi for the purpose of restoring the honor or something of the republic. This is all explored in the new book, "Millennium Falcon" in which the Falcons past is traced. StarWars.com had an article on it for awhile confirming the rumors.)