One or more computer systems, a carrier medium, and a method are provided for creating a catalog for backup data using NDMP file history messages. The messages are received at a first computer system (NDMP client) from a second computer system (NDMP host). Each message comprises information describing a filesystem node (a file or directory). The messages comprise hierarchy information and attribute information for the nodes. For each message comprising hierarchy information, an entry may be created for the respective node in a catalog, and the hierarchy information for the respective node may be stored in the catalog. For each message comprising attribute information, the attribute information for the respective node may be stored in the catalog. The messages may be processed in a single pass without caching them all. A carrier medium may include program instructions which, when executed, cause the above operations on one or more computer systems.