The Bowen Basin of Queensland and the Hunter Valley of New South Wales are the two largest black coal producing areas in Australia. Mining activities require the availability of large on-lease storages for water and tailings. The legislative framework for the regulation of large dams is slightly different between the states. The paper provides a broad outline of the regulatory framework in each state, with particular reference to Queensland and New South Wales. In New South Wales, water storages and tailings dams are treated similarly by the regulator. Under the Queensland Water Act 2000, now proclaimed, referable dams are restricted to water supply dams the failure of which involves population at risk downstream. Tailings dams are excluded, being deemed hazardous waste dams regulated under the Environment Protection Act 1994. These storage facilities are required to include a design storage allowance' so that the possibility of spillway discharges is minimised. New South Wales is moving toward this requirement. A curious anomaly is emerging in Queensland: the legislative definition of hazardous waste - material resulting from the processing of minerals - does not extend to coal tailings since coal is not included in the definition of a mineral. The paper explores this and other ramifications for mining operations of the new legislation as well as general trends in criteria affecting the cost of providing water and tailings storages.