The Gulf killifish, Fundulus grandis, is a small teleost fish that inhabits marshes of the Gulf of Mexico and demonstrates high tolerance of environmental variation, making it an excellent subject for the study of physiological and molecular adaptations to environmental stress. In the present study, two-dimensional (2D) gel electrophoresis and matrix-assisted laser desorption/ionization time-of-flight tandem mass spectrometry were used to resolve and identify proteins from five tissues: skeletal muscle, liver, brain, heart, and gill. Of 864 protein features excised from 2D gels, 424 proteins were identified, corresponding to a 49% identification rate. For any given tissue, several protein features were identified as the same protein, resulting in a total of 254 nonredundant proteins. These nonredundant proteins were categorized into a total of 11 molecular functions, including catalytic activity, structural molecule, binding, and transport. In all tissues, catalytic activity and binding were the most highly represented molecular functions. Comparing across the tissues, proteome coverage was lowest in skeletal muscle, due to a combination of a low number of gel spots excised for analysis and a high redundancy of identifications among these spots. Nevertheless, the identification of a substantial number of proteins with high statistical confidence from other tissues suggests that F. grandis may serve as a model fish for future studies of environmental proteomics and ultimately help to elucidate proteomic responses of fish and other vertebrates to environmental stress.