With a team of thirty-five people, Shadow of the Colossus began development in 2002 under the project name “Nico” and was intended to be a direct sequel to Ico. The name “Nico” itself is a portmanteau of the Japanese word ni (“two”) and “Ico”. An early technology demo for the project shown at the DICE Summit in 2003 depicted a group of masked, horned boys riding horses while attacking and defeating a colossus. However, Fumito Ueda expressed that, at the time, it was simpler to reuse the character design of Ico’s protagonist, and that he never explicitly desired a sequel to Ico. Japanese pre-orders of Shadow of the Colossus later included a bonus DVD with the concept video, a trailer describing Nico’s plot, and an introduction the development team states they wanted to use in Shadow of the Colossus. [info from Wikipedia]
If you are interested, you can read more about Shadow of the Colossus Beta and see some of the removed colossi that were created during the development of the game.