SotC and ICO's connection as well as timelines are left up to personal interpretation. The games' creator has gone on record saying he had no idea in mind as to how they both intertwine while creating them other than the fact they both take place in the same world.
Most fans believe SotC is a prequel due to the ending which reveals a baby with a "certain condition".
Have a look at this (slightly spoiler laden) bit from Wikipedia:
Shadow of the Colossus is considered both a spiritual successor
and prequel to Ico. For several months during and after the game's
release, the game's director and lead designer, Fumito Ueda,
maintained that the game's status as a prequel was simply his personal
take on the game and not necessarily its canon nature, as he largely
intended for players to decide the specifics of the story for
themselves, but he confirmed the two do have a connection.
Moreover, the shadowy figures which appear in the Shrine of Worship
are connected to the shadows which the player must fight in Ico.
Both games feature "horned" characters for protagonists (Wander
sprouts horns at the end of the game). The Queen's Sword from Ico is
also available as a bonus unlockable item. Both games also use
unique fictional languages.