I was watching a baseball game and saw the outfielder partially climb the wall in the outfield to try and rob a homerun. This made me wonder: can an outfielder climb over the outfield fence and stand in the bleachers? Or does he need to be in fair territory when a pitch is thrown?
First of all, yes the fielder must start the play in fair territory.
5.02 Fielding Positions
When the ball is put in play at the start of, or during a game, all fielders other than the catcher shall be on fair territory.
You mentioned partially climbing a wall. Climbing upon a wall (but not beyond) is specifically allowed. From a comment to 5.09(a)(1):
A fielder may reach over a fence, railing, rope or other line of demarcation to make a catch. He may jump on top of a railing, or canvas that may be in foul ground.
But that doesn't give permission to leave the field entirely and go into the stands. The MLB Umpire Manual is a bit more explicit here (my bolding):
The fielder is confined to the limits of the playing field, but may reach over any fence, railing, or any line of demarcation to make a catch. The fielder may also jump on top of a railing marking the boundary of the field or on any tarp that may be on foul ground in order to make a play. (See also Section 8.1 [Legal Catch].)
8.1 LEGAL CATCH
A fielder may not jump over any fence, railing, or rope marking the limits of the playing field in order to catch the ball. A fielder may (1) reach over such fence, railing, or rope to make a catch;
So a fielder can climb the fence. And in the process of making a catch can fall over the fence. But the fielder is not allowed beyond the fence before making the catch. Standing in the bleachers to make a play on a batted ball is not allowed. A fielder doing so would not be awarded a legal catch.