Urban parks are one of the main natural components of an urban ecosystem, bringing great ecological, economic, and social benefits and playing an important role in ecosystem sustainability. The recreational functions of urban parks typically receive increasing concern as citizens living standards increase. Residents are concerned about not only the quantity and quality of urban parks provided by the government, but also whether they can reach and enjoy urban parks conveniently. Can current urban parks satisfy the demand of citizens in a city and is the spatial distribution of parks reasonable? How can the spatial distribution of urban parks in a city be optimized for maximum benefits? Research on these questions is a prerequisite to planning and managing urban parks reasonably. In the past, answers to these questions were mainly acquired by questionnaire or statistical indices. However, both of these methods are deficient when evaluating the spatial distribution and service of urban parks, leading to increased attention to the issue of accessibility. The methods commonly used to evaluate accessibility (simple buffering, minimum distance, gravity model, and cost weighted distance) also have shortcomings, because they cannot measure the distance between urban parks and leisure users realistically. Network analysis solves this problem by measuring the distance of actual routes followed by leisure users. To test the usefulness of network analysis when evaluating urban park accessibility and to acquire comprehensive information about the current status of accessibility and service of Shenyangs urban parks, we studied the accessibility and service of urban parks in Shenyang and its eight districts based on road and population distribution data using Network Analyst model in ArcGIS 9.2. The results showed that: (1) The method of GIS-based network analysis is more precise than the simple buffering method when calculating urban park accessibility, and two service indicators (service area ratio and service population ratio) are better than the conventional statistical indicators used to quantify service status of urban parks. (2) Using network analysis, only 19.47% of the study area and 43.41% of the citizens are served based on the criterion that an urban park has a service radius of 900 meters (15 minutes walk). Shenyangs urban parks are inadequate in quantity and distributed uneven spatially. (3) The spatial distribution of Shenyangs urban parks and their service in the downtown area was better than that in the suburbs. Urban park accessibility was highest in Shenhe, Heping, and Huanggu Districts, while that in Dongling, Tiexi, and Dadong Districts was in middle place. Urban parks provision and accessibility was the most inadequate and problematic in Yuhong and Hunnan Districts. Our case study of the accessibility and service of Shenyangs urban parks indicated that the method of GIS-based network analysis evaluates the accessibility of urban parks exactly, and it can also be used to quantify the provision of and access to a range of urban services (schools, supermarkets, and medical institutions). Whats more, the knowledge acquired about the accessibility and service of Shenyangs urban parks provided precise information useful for optimizing their spatial distribution.