One of the main motivations for building treebanks is that they facilitate the development of syntactic parsers, by providing realistic data for evaluation as well as inductive learning. In this paper we present what we believe to be the first robust data-driven parser for Bulgarian, trained and evaluated on data from BulTreeBank (Simov et al., 2002). The parser uses dependency-based representations and employs a deterministic algorithm to construct dependency structures in a single pass over the input string, guided by a memory-based classifier at each nondeterministic choice point, as described in Nivre et al. (2004). Since the original BulTreeBank annotation is based on HPSG, it has been necessary to extract dependency structures from the original annotation both for training and evaluating the parser. The paper is structured as follows. Section 2 introduces the MaltParser system used in the experiments to induce parsers from treebank data. Section 3 presents BulTreeBank, and section 4 shows how the BulTreeBank annotation can be converted into a dependency structure annotation of the kind required by MaltParser. Section 5 describes the experimental conditions, and section 6 discusses the results of the experiments. Section 7 contains our conclusions.