Detrimental effects of introduced fishes on native amphibian populations have prompted removal of introduced cutthroat (Oncorhynchus clarki), rainbow (Oncorhynchus mykiss), and brook trout (Salvelinus fontinalis) from naturally fishless lakes at Mt. Rainier National Park, Washington (U.S.A.). Using paleolimnological indicators (diatoms, invertebrates, and sediment characteristics) in eight 480-year-old sediment cores from eight lakes, we (1) derived estimates of baseline environmental conditions and natural variation, (2) assessed the effects of stocking naturally fishless lakes, and (3) determined whether lakes returned to predisturbance conditions after fish removal (restoration). Diatom floras were relatively stable between 315 and 90 years before present in all lakes; we used this time period to define lake-specific "baseline" conditions. Dissimilarity analyses of diatoms revealed sustained, dramatic changes in diatom floras that occurred approximately 80 years ago (when fish were introduced) in four of five stocked lakes, whereas the diatom floras in two unstocked lakes had not changed significantly in the last 315 years. Diatoms were not preserved in an eighth lake. State changes also occurred in two lakes over 200 years before European settlement of the Pacific Northwest. Preserved invertebrate densities fluctuated dramatically over time in all cores, providing a poor reference for assessing the effects of fishes. Nevertheless, fish-invertebrate interactions have been demonstrated in other paleolimnological studies and may be useful for lower-elevation or more productive lakes. Because diatom communities have not returned to predisturbance assemblages in restored lakes, even 20-30 years after fish removal, we conclude that Mt. Rainier lakes were not successfully restored by the removal of fishes.