The size of the Hilbert space for a multiqubit state scales exponentially with the number of constituent qubits. Often this leads to a similar exponential scaling of the experimental resources required to characterize the state. Contrary to this, we propose a physically motivated method for experimentally assessing the fidelity of an important class of entangled states known as cluster states. The proposed method always yields a lower bound of the fidelity with a number of measurement settings scaling only linearly with the system size, and is tailored to correctly account for the errors most likely to occur in experiments. For one-dimensional cluster states, the constructed fidelity measure is tight to lowest order in the error probability for experimentally realistic noise sources and thus closely matches the true fidelity. Furthermore, it is tight for the majority of higher-order errors, except for a small subset of certain nonlocal multiqubit errors irrelevant in typical experimental situations. The scheme also performs very well for higher-dimensional cluster states, assessing correctly the majority of experimentally relevant errors.