Attapulgite is a kind of silicate with a nano-sized rod-like morphology. In this research, a novel nanocomposite hydrogel based on cellulose and attapulgite was fabricated by a facile method and its adsorption properties for methylene blue were investigated. First, cellulose was dissolved in 7 wt% NaOH/12 wt% urea solution within 2 min, and then cellulose was cross-linked with sodium alginate by epichlorohydrin in presence of attapulgite at 50 °C for 4 h. By this facile approach, cellulose–attapulgite nanocomposite hydrogel was fabricated. SEM observation showed that nanocomposite hydrogel exhibited a porous structure and rough inner surface and attapulgite was incorporated inside. The FTIR and XPS spectra confirmed the cross-linking between cellulose and sodium alginate. The swelling experiment results revealed that sodium alginate enhanced the swelling property of cellulose hydrogel. Swelling degree of cellulose–alginate increased from 36.9 to 42.8 with the increase of sodium alginate content, while swelling degree of pure cellulose hydrogel was 36.3. The addition of attapulgite reduced the swelling degree of nanocomposite hydrogel. Attapulgite enhanced the adsorption capacity of nanocomposite hydrogel compared to the hydrogel without attapulgite. The maximum adsorption capacity of nanocomposite hydrogel was 24.3 mg g−1. Further adsorption kinetics and adsorption isotherm experiments showed that the pseudo-second-order adsorption model and Freundlich model best described the adsorption kinetics and isotherm, respectively. These results suggest that the nanocomposite hydrogel prepared by this facile method can be used in removing dyes from wastewater.