The invention provides recombinant adenoviral vectors which are capable of eliciting immunity against the pre-erythrocytic stage of the life cycle of the malaria parasite. In particular, the invention provides a recombinant, replication deficient simian adenoviral vector which encodes an antigen comprising the thrombospondin-related adhesion protein (TRAP), and also immunogenic compositions (e.g. vaccines) comprising the vector and methods of using such compositions.