The frequency shift of a nanomechanical sensor carrying a nanoparticle is studied. A bridged single-walled carbon nanotube (SWCNT) carrying a nanoparticle is modeled as a clamped micro-beam with a concentrated micro-mass at any position. Based on the nonlocal Timoshenko theory of beams, which incorporates size effects into the classical theory, the natural frequencies of the nanomechanical sensor are derived using the transfer function method. The effects of the mass and position of the nanoparticle on the frequency shift are discussed. In the absence of the nonlocal effect, the frequencies are reduced to the results of the classical model, in agreement with those using the finite element method. The obtained results show that when the mass of the attached nanoparticle increases or its location is close to the beam center, the natural frequency decreases, but the shift in frequency increases. The effect of the nonlocal parameter on the frequency shift is significant. Decreasing the length-to-diameter ratio also increases the frequency shift. The natural frequencies and shifts are strongly affected by rotary inertia, and the nonlocal Timoshenko beam model is more adequate than the nonlocal Euler-Bernoulli beam model for short nanomechanical sensors. The obtained results are helpful in the design of SWCNT-based resonator as nanomechanical mass sensor.