A parallel tight-binding molecular dynamics with an order-N [O(N))] algorithm is implemented to perform large-scale simulation of nanostructured materials. The algorithm is based on the Fermi-operator expansion of an electronic energy and force, and we present its basic formalisms. Accuracy necessary for molecular-dynamics simulations can be obtained by a proper truncation in the expansion. Parallel efficiency on a parallel PC cluster shows nearly ideal scaling behavior with respect to the number of processors. Applicability of the method to a silicon-carbide system is examined.