While they are an effective tool for studying landscape patterns and describing land-use change, landscape metrics are sensitive to variation in spatial grain sizes. It is therefore crucially important to select an optimal grain size for characterizing urban landscape patterns. Due to accelerated urbanization, Shanghai, the economic capital of China, has seen drastic changes in landscape patterns in recent decades and it would be interesting to take Shanghai as an example for examining the grain effect of landscape patterns. In this study, from Shanghai’s land use maps derived from Landsat images of 1998, 2007, and 2017 via random forest classification, a selection of landscape metrics was measured with 14 grain sizes ranging from 30 m to 460 m. Both the conventional first scale domain method and the information loss evaluation model were adopted to comprehensively determine an optimal grain size for characterizing Shanghai’s landscape pattern. After that, the land use dynamic degree model was used to explore the change in Shanghai’s landscape pattern under the optimal grain size. Results demonstrate that (1) the responses of landscape metrics varied with grain size, which could be divided into three categories, namely irregular trend, decreasing trend, and no clear change; that (2) the optimal spatial grain size for landscape pattern analysis was 60 m; and that (3) the degree of landscape aggregation decreased, whereas that of landscape diversity and fragmentation increased. This study shows a clear grain effect of landscape patterns and can provide useful insights for urban landscape planning.