To clarify that, prior to the Atlantic Ocean there was a "pro-Atlantic" ocean known as the Iapetus. Around 250 million years ago (during the Permian Period) it had closed up completely as Europe and Africa (slooowly) collided with North and South America forming the supercontinent of Pangea. The Appalachian mountains were a product of the collision, though now much reduced by over 200 million years of erosion.
Around 200 mya (during the Triassic Period) Pangea began to split apart along a looong crack in the crust and the current Atlantic Ocean began to form. Both of the land masses on the North and South America side as well as those on the Africa, European side (including Australia and Antarctica) more or less stayed attached to their respective portions of the former supercontinent.
It was, as you stated, millions of years later (during the Cretaceous Period) that the Africa/Europe/Australia/Antarctica side of the former supercontinent split into the continents we know today.
Supercontinents are inherently unstable because, being so large, they act as heat blankets. Heat from below builds up and ultimately fractures these huge landmasses into smaller, but still quite large, separate land massess.
