We examine size and frequency dependent gas damping of nanobeam resonators. We find an optimal beam width that maximizes the quality factor at atmospheric pressure, balancing the dissipation that scales with surface-to-volume ratio and dominates at small widths, against the interaction with the underlying substrate via the air that dominates the behavior of the wider devices. This latter interaction is found to affect the Knudsen number corresponding to a transition out of the molecular damping regime. We examine higher order modes and tune tension mechanically to vary the frequency of individual resonators, to resolve size and frequency effects. © 2008 American Institute of Physics.