An exact dynamic stiffness method is introduced for investigating the free vibration characteristics of the steel-concrete composite beams consisting of a reinforced concrete slab and a steel beam which are connected by using the stud connectors. The elementary beam theory is used to define the dynamic behaviors of the two beams and the relative transverse deformation of the connectors is included in the formulation. The dynamic stiffness matrix is formulated from the exact analytical solutions of the governing differential equations of the composite beams in undamped free vibration. The application of the derived dynamic stiffness matrix is illustrated to predict the natural frequencies and mode shapes of the steel-concrete composite beams with seven boundary conditions. The present results are compared to the available solutions in the literature whenever possible.