Beam string structures (BSS) are frequently employed in large-span spatial structures due to their high load-carrying efficiency and elegant appearance. Owing to the neglection of the influence of prestress, the natural frequency of the BSS is often overestimated which could be crucial to the dynamic behavior of BSS. This paper presents an exact matrix stiffness analysis method (MSM) for investigating the relationship between prestress and natural frequency of the planar BSS. A novel dynamic stiffness matrix of beam-columns considering natural frequency and axial force is used to develop the MSM. The proposed MSM with the exact dynamic element stiffness matrix for the dynamic analysis of the BSS are verified by comparing with previous results based on the finite element method. The illustrative examples demonstrate that the prestress in the cable has a negative effect on the natural frequency of the BSS and should be considered in the dynamic analysis.