Shadow of The Colossus was originally planned around groups of characters on horses working cooperatively to defeat the colossi. However, this was cancelled due to it being too difficult for the Playstation 2's hardware.
Contributed by TheProJamer
Acording to an interview in the Shadow of the Colossus Official Artbook and Guidebook, there were plans to have the ending change If the player had Ico save data on their memory card.
Spoiler:There was also the idea that Momo would have woken up and reunited with Wonder before Lord Emon sealed him away. Wonder would have had an irreversible beast form instead of the demon baby form he has in the final version. This idea was dropped because the development team felt the current ending was better.
Contributed by gamemaster1991
Ueda wished the game to have a unique presentation and change how both players and developers would perceive what bosses should be in video games. To ensure that the programmers focused entirely on the colossi boss battle quality, he limited the enemies to just the sixteen colossi, that could only be approached one at a time, and have various behavior patterns.

Though limiting the presence of enemies to only bosses was partly intended to differentiate the game from others, Ueda also expressed that it was to ensure that the programmers' focus was entirely on the colossi so that their quality would be as high as possible.
Contributed by DrakeVagabond
Kaido challenged the programmers to meet the concept of realistic physics in relation to the movement of the colossi and the subsequent effect this movement would have for Wander, both in terms of how he might be displaced and how he may be able to use this movement to his advantage. For instance, if a colossus were to shake, Kaido wanted Wander's position to shift realistically in response. Additionally, if a colossus' limb was currently horizontal, Kaido wanted the player to be able to run across the limb as though it were any other flat surface. He referred to these two concepts as "player dynamics and reactions" and "organic collision deformation".
Contributed by DrakeVagabond
The game was at one point in early development going to feature multiplayer. Back when it was Project Nico, a 2003 tech demo depicted a group of masked, horned boys riding horses while attacking and defeating a colossus. This feature was ultimately dropped from the final product.

Fumito Ueda and Kenji Kaido (producer) revealed that it was merely a technical demo designed to show off the interaction mechanics between the hero and Colossus. The creation of the demo was more important than the creation of entirely new characters, so they had simply used an existing character model for the demo.
Contributed by DrakeVagabond
Ueda and producer Kenji Kaido held their team to a high standard throughout production. An admitted perfectionist, Ueda felt that only one or two out of 500 artists who applied to work on Shadow of the Colossus met his criteria, and often demanded thorough changes in design until it matched his vision
Contributed by DrakeVagabond
With a team of thirty-five people, Shadow of the Colossus began development in 2002 under the project name Nico (Next Ico) and was intended to be a sequel to Ico.
Contributed by DrakeVagabond
It's possible to grab onto birds and fish and catch a ride.
Contributed by MidnaLove
Attachment
There's an unused item in the game's code called The Eye of the Colossus. While semi-functional in the Preview version of the game, it was removed from the final game. It allows players to witness battles through the eyes of the Colossus they are fighting. It is, however, buggy and unfinished. Two pieces of unused text describing the item also remain within the game.
Contributed by DidYouKnowGaming
None of the colossi have official names. The names that fans go by and that are in the guide book are nicknames that the developers gave each of them to distinguished between them.
Contributed by gamemaster1991
Shadow of the Colossus was originally going to have 48 Colossi, but that number was cut down to 24, and finally to 16. Some of the designs were fully fleshed out.
Contributed by DidYouKnowGaming
Agro will occasionally ignore commands, as Fumito Ueda (lead designer) believed that "a real horse ... doesn't always obey. It's not like a car or a motorcycle, it won't always turn when you say 'turn!'"

He also admitted that the team had to work out a good balance of how often Agro would ignore commands to allow for playability over realism.
Contributed by Dazz