We study the generation and evolution of density perturbations and pec
uliar velocities due to primordial magnetic fields. We assume that a r
andom magnetic held was present before recombination and follow the he
ld's effect on the baryon fluid starting at recombination. We find tha
t magnetic fields generate growing density perturbations on length sca
les larger than the magnetic Jeans length, I,, and damped oscillations
for scales smaller than lambda(B). For small wavenumbers k (large len
gth scales), we find that the magnetic field-induced density power spe
ctrum generally scales as k(4). We derive the magnetic Jeans length ex
plicitly by including the back-reaction of the velocity held onto the
magnetic held and by decomposing the magnetic field into a force-free
background held and perturbations about it. Depending on the strength
of the magnetic field and the ultraviolet cutoff of its spectrum, stru
cture can be generated on small or intermediate scales early in the hi
story of the universe. For a present rms magnetic held of 10(-10) G on
intergalactic scales, we find that perturbations on galactic scales c
ould have gone nonlinear at z similar or equal to 6. Finally, we discu
ss how primordial magnetic fields affect scenarios of structure format
ion with nonbaryonic dark matter.