Understanding the spatiotemporal evolution of rocky desertification is crucial for regional ecosystems and the environmental stability. Currently, some studies have focused on extracting the area and level in transition of karst rocky desertification (KRD) using bi-temporal or multi-temporal remote sensing data, but ignoring the evolutionary mechanism of KRD. This study aimed to capture complex spatiotemporal interaction relationship, namely spatial-temporal connection paths (i.e., evolution trajectories), time span of evolution (i.e., evolution behaviors), and shifts of transition types (i.e., evolution states) based on spatiotemporal graph of KRD patches from dense long time-series Landsat images. This study selected Pingguo County, a typical KRD region as the study area, which is located in Guangxi Province, southwest China. And all available Landsat images covering the entire study area from 2001 to 2023 were collected. In this study, annual KRD level maps based on vegetation coverage and bare rock coverage were first obtained. Then spatiotemporal graph was established to detect evolution trajectory of KRD patches. Finally, this study developed evolution behaviors, evolution states, and key landscape metrics in KRD. The main results were as follows. (1) Potential KRD regions have significantly expanded to other more severe KRD regions, while landscape metrics further revealed structural simplification in extreme KRD regions and persistent fragmentation in moderate and severe KRD regions. (2) The evolution trajectories of most KRD levels were mainly characterized by merging, shrinkage, and dissipation. Light and moderate KRD showed complex tree-like dynamics, whereas severe KRD exhibited a steady recovery trend. (3) Short-term and complex behaviors dominated different KRD evolution trajectories, in which three primary evolution patterns have emerged in the evolutionary state, namely from expansion to dissipation, from expansion to splitting to dissipation, and from shrinkage to dissipation. This study used a graph-based spatiotemporal framework to capture complex evolution dynamics of rocky desertification, such as short-term abrupt changes and lagged responses, thereby offering new insights into karst landscape change. The proposed method is also adaptable to analyze the spatiotemporal evolution characteristics of other ecological problems.