Announced at E3 2001, Yoshi's Story (ヨッシーストーリー, Yoshi Story) is a stage in Super Smash Bros. Melee. It is a very basic, neutral stage, similar in structure to Battlefield. The bottom part is primarily flat with the left and right side sloped down at a minor angle. There are three platforms that float above the bottom platform: A low left one, a high middle one, and a low right one. The main platform has walls which continue to the bottom of the stage, unlike Battlefield, so that characters cannot become stuck on the bottom trying to recover. The lack of intrusive stage elements aside from the moving cloud makes this a neutral stage for tournaments.
The stage also features a small floating cloud, colloquially dubbed "Randall" (see below). Additionally, there are Shy Guys which fly around in groups of 1-6 in a line. If items are enabled, specifically food, the Shy Guys will be holding food which they release onto the stage when hit. Even when food is not present, Shy Guys can affect gameplay: they will interfere with projectiles, and moves such as Green Missile and Raptor Boost, and they are useful for countering stale-move negation, through hitting them with attacks not commonly used.
Pak E. Derm can be seen pacing back and forth in the background.
Randall the Cloud
Randall the Cloud is a nickname for the Lakitu's Cloud featured on this stage. It moves in a rectangle through the bottom of the stage. It is possible to hang/stand/edgeguard on the cloud until it goes back into the stage. It is often used to assist the recovery process. The term derived originally from Canadian smasher FastFox, and it has since taken off as a norm on SmashBoards. It is also mentioned commonly in competitive Melee matches, usually when a player chooses to land on it instead of aiming for the edge while recovering, or when it comes out and saves a recovering player who otherwise would've been edgehogged.
Randall does not appear for the opening ten seconds of a given battle and emerges on the right-hand side of Yoshi's Story immediately thereafter, completing a trip through the stage and out the other side in 20 seconds. This means that the position of the cloud is consistent and predictable, not random. Through paying particular attention to the countdown in a timed match, a prudent smasher can use this knowledge to effectively stall a recovery and land on Randall instead of falling.
Randall the Cloud can also be used for taunt canceling.
This stage is from Yoshi's Story for the Nintendo 64. In Yoshi's Story, Yoshi's Island is turned into a storybook because of Baby Bowser. The levels are, therefore, taken place inside the book. Many things in the story are made out of cardboard (including the clouds, glass, hills, etc), among other materials (like denim, as seen in the image to the left). In this stage in Melee many of the same things are made out of cardboard (indeed, if one pauses and moves the camera around the stage, one will have the impression of it taking place inside a cardboard box). In the first level of Yoshi's Story one can see in the background that the sky is taped together, has a broken glass symbol, and a square with two lines under a six. In the second level one can see water waves in the background with distant islands. In this stage all of this is retained. In the second level of Yoshi's Story the grass and trees is made out of a cloth like material. In this stage one can see on the main bottom platform is edged with this same material and the leaves of the tree is made out of it too. In Yoshi's Story the player has to walk along a path throughout the levels. In this stage a path can be seen that goes across the main bottom platform. In Yoshi's Story there is a character named "Pak E. Derm". He blocks players from proceeding through the path. He can be seen wandering in the background of this stage. At a certain point in Yoshi's Story the player has to ride a cloud that follows a line as means for transportation. The cloud can be seen at the bottom of this stage and he can still be rode on. Also from Yoshi's Story are "Fly Guys", which are flying Shy Guys, who hold fruit while flying around. If Yoshi managed to eat the fruit they would fly away. In this stage the Fly Guys carry fruit. When the player attacks a Fly Guy it drops the food and flies away. 
The track that plays on this stage is a mix between the first level of Yoshi's Story and Yoshi's Story's title screen.