This study reports the synthesis of a novel graphene/chitosan/β-cyclodextrin composite material (GO/CS/β-CD) via a onestep chemical reduction method, which combines the advantages of graphene, chitosan, and β-cyclodextrin. The morphology and structure of the composite were characterized using various techniques, such as scanning electron microscopy (SEM), Fourier transform infrared spectroscopy (FTIR), and Raman spectroscopy. Subsequently, sortase A (SA) was immobilized onto the GO/CS/β-CD for the detection of Staphylococcus aureus. The sensor exhibited a good linear relationship within the concentration range of 30–300 CFU/mL, with a detection limit of 12 CFU/mL. The GO/CS/β-CD composite material showed enhanced properties due to the synergistic effect of graphene, chitosan, and β-cyclodextrin. The immobilization of sortase A onto the composite material improved the sensitivity and selectivity of the sensor for the detection of S. aureus. This study presents a novel graphene/chitosan/β-cyclodextrin composite material with immobilized sortase A, demonstrating enhanced sensitivity and selectivity for the detection of Staphylococcus aureus, which has potential for the development of high-performance sensors in various fields.