In the framework of the Gurtin–Murdoch model, the buckling features are studied for nonlinearly elastic cylindrical tubes with surface stresses under two different types of combined loading. The exact neutral equilibrium equations are derived, and the linearized boundary-value problem is formulated by solving which the stability of these tubes is analyzed. For an aluminum tube, the critical curves were found numerically and the stability regions were constructed in the planes of the corresponding loading parameters. It follows from their analysis that surface stresses can have both stabilizing and negative influence on the buckling of nonlinearly elastic tubes, depending on the type of loading. The degree of this influence is determined by the overall size (scale) of the tube.