The Flood was never introduced in the storyline yet. Halo: Reach (in order of events) was the first thing to happen, then Halo Wars, Halo: CE, Halo 2, Halo 3: ODST, then Halo 3. Technically, the Flood was discovered after ODST and before Halo 3.
^ This person is wrong. Firstly, the events of Halo Wars occur before those of Halo: Reach. The rest of the chronology is correct. However, the Flood is first introduced in Halo: Combat Evolved as the crew of the Pillar of Autumn are searching the Halo ring for a way to use it as a weapon against the Covenant. The Flood were stored dormant on the ring, presumably as part of studies the Forerunners were conducting to discover a way to defeat them.