In this paper the problem of recursive structural dynamics identification from noise-corrupted observations is addressed, and approaches that overcome the weaknesses of current methods, stemming from their underlying deterministic nature and ignorance of the fact that structural systems are inherently continuous-time, are introduced. Towards this end the problem is imbedded into a stochastic framework within which the inadequacy of standard Recursive Least Squares-based approaches is demonstrated. The fact that the continuous-time nature of structural systems necessitates the use of compatible triples of excitation signal type, model structure, and discrete-to-continuous transformation for modal parameter extraction is shown, and two such triples constructed. Based on these, as well as a new stochastic recursive estimation algorithm referred to as Recursive Filtered Least Squares (RFLS) and two other available schemes, a number of structural dynamics identification approaches are formulated and their performance characteristics evaluated. For this purpose structural systems with both well separated and closely spaced modes are used, and emphasis is placed on issues such as the achievable accuracy and resolution, rate of convergence, noise rejection, and computational complexity. The paper is divided into two parts: The problem formulation, the study of the interrelationships among excitation signal type, model structure, and discrete-to-continuous transformation, as well as the formulation of the stochastic identification approaches are presented in the first part, whereas a critical evaluation of their performance characteristics based on both simulated and experimental data is presented in the second.