That happened before the Garden of Eden incident. Before then, he walked in heaven (on the holy mount of God).
Ezekial 28:14-15 (NIV)
14 You were anointed as a guardian cherub, for so I ordained you.
You were on the holy mount of God; you walked among the fiery
stones. 15 You were blameless in your ways from the day you were
created till wickedness was found in you.
He was actually cast down because he became proud.
Ezekial 28:17 (NIV)
Your heart became proud on account of your beauty, and you
corrupted your wisdom because of your splendor. So I threw you to
the earth; I made a spectacle of you before kings.
Then he thought that he could be God, that he could take God's place in the universe as ruler of it:
Isaiah 14:13-14 (NIV)
13 You said in your heart, “I will ascend to the heavens; I will
raise my throne above the stars of God; I will sit enthroned on
the mount of assembly, on the utmost heights of Mount Zaphon. 14 I will ascend above the tops of the clouds;
I will make myself like the Most High.”
That was his downfal: Pride--he thought he was as good as God.