A novel formulation for tight binding total energy calculations and tight binding molecular dynamics, which scales linearily with the size of the system, is presented. The linear complexity allows us to treat systems of very large size and the algorithm is already faster than the best implementation of classical diagonalization for systems of 64 atoms. In addition, it is naturally parallelizable and it permits us therefore to perform molecular dynamics simulations of systems of unprecedented size. Finite electronic temperatures can also be taken into account. We illustrate this method by investigating structural and dynamical properties of solid and liquid carbon at different densities.