Yellowstone Protection Act of 1996 - Provides that specified lands located upstream of Yellowstone National Park, Absaroka-Beartooth National Wilderness Area, and the Clarks Fork of the Yellowstone National Wild and Scenic River within the Gallatin and Custer National Forests in Montana (the Area) that are segregated from entry under the general mining laws pursuant to executive order shall not be: (1) open to location of mining claims under U.S. general mining laws; (2) available for leasing under U.S. mineral and geothermal leasing laws; and (3) available for disposal of mineral materials under the Materials Act of 1947.

Prohibits: (1) patents under the general mining laws from being issued for claims located in the Area; (2) Federal lands within such Area from being used in connection with mining related activities, except for reclamation; or (3) Federal departments or agencies from assisting in the development or construction of impoundment structures for the storage of mine tailings, work camps, powerplants, electrical transmission lines, gravel or rock borrow pits or mills within the Area. Provides that nothing in this Act shall limit reclamation.

Subjects any mining or mining related activities occurring in the Area to operation and reclamation requirements established by the Secretary of Agriculture.

Requires the Secretary of the Interior to review mining claims within the Area and to declare invalid claims null and void.

Prohibits the Secretary of Agriculture from approving a plan for mining operation activities within the Area that: (1) threaten to pollute groundwater or surface water; or (2) require the perpetual treatment of acid mine pollution of surface or groundwater resources.

Sets forth plan approval procedures.