A parallel tree labeling apparatus and method for processing an eXtensible Markup Language document (XML). The parallel tree labeling apparatus for processing an XML document includes a data distributor configured to divide the XML document into a plurality of data blocks; and a labeling component configured to receive elements of each of the plurality of data blocks, perform a labeling procedure on the plurality of data blocks in parallel, and generate a final label by combining partial labels.