The domain-shape-sensitivity of structural natural frequencies is determined using a new finite-element approach called the fixed-basis-function finite-element approach. The approach adopts the point of view that the finite-element grid is fixed during the sensitivity analysis; therefore it is referred to as a ‘Fixed Basis Function Shape Sensitivity’ finite-element analysis. This approach avoids the requirement of explicit or approximate differentiation of finite-element matrices and vectors and the difficulty or errors resulting from such calculations. Effectively, the sensitivity to boundary shape change is determined exactly; thus the accuracy of the solution sensitivity is dictated by the accuracy of the finite-element analysis. The sensitivity analysis is undertaken within the context of Rayleigh’s principle and is developed in quite general terms. It is shown that the evaluation of sensitivity matrices involves only modest calculations beyond those for the finite-element analysis of the reference problem; certain boundary integrals on the reference location of the moving boundary are required. In addition, boundary reaction forces and sensitivity boundary conditions must be evaluated. The present formulation separates solution sensitivity from finite-element grid sensitivity and provides a unique representation of boundary perturbations within the context of isoparametric finite-element formulations. The work is illustrated for beam as well as plate problems. Excellent agreement is obtained for shape-sensitivity calculations that compare exact solutions, fixed-basis finite-element results, and overall finite-difference approximations to the finite-element sensitivity results. It is illustrated that the finite-element eigenvalue problem and the fixed-basis finite-element eigenvalue-sensitivity results exhibit similar accuracy and convergence characteristics.