Coupled, dynamical spin-lattice models provide a unique test ground for simulations investigating the finite-temperature magnetic properties of materials under the direct influence of the lattice vibrations. These models are constructed by combining a coordinate-dependent interatomic potential with a Heisenberg-like spin Hamiltonian, facilitating the treatment of both the atomic coordinates and the spins as explicit phase variables. Using a model parameterized for bcc iron, we study the magnetic phase transition in these complex systems via the recently introduced, massively parallel replica-exchange Wang-Landau Monte Carlo method. Comparison with the results obtained from rigid lattice (spin-only) simulations shows that the transition temperature as well as the amplitude of the peak in the specific heat curve is marginally affected by the lattice vibrations. Moreover, the results were found to be sensitive to the particular choice of interatomic potential.