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 hangar, 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 landing. 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. This is all explored in the new book -- Millennium Falcon -- in which the Falcon's past is traced. StarWars.com had an article on it for a while, confirming the rumors.