Although malaria is one of the oldest and most widely distributed diseases affecting humans, identifying and characterizing its presence in ancient human remains continue to challenge researchers. We attempted to establish a reliable approach to detecting malaria in human skeletons using multiple avenues of analysis: macroscopic observations, rapid diagnostic tests, and shotgun-capture sequencing techniques, to identify pathological changes, Plasmodium antigens, and Plasmodium DNA, respectively. Bone and tooth samples from ten individuals who displayed skeletal lesions associated with anaemia, from a site in southern Egypt (third to sixth centuries AD), were selected. Plasmodium antigens were detected in five of the ten bone samples, and traces of Plasmodium aDNA were detected in six of the twenty bone and tooth samples. There was relatively good synchronicity between the biomolecular findings, despite not being able to authenticate the results. This study highlights the complexity and limitations in the conclusive identification of the Plasmodium parasite in ancient human skeletons. Limitations regarding antigen and aDNA preservation and the importance of sample selection are at the forefront of the search for malaria in the past. We confirm that, currently, palaeopathological changes such as cribra orbitalia are not enough to be certain of the presence of malaria. While biomolecular methods are likely the best chance for conclusive identification, we were unable to obtain results which correspond to the current authentication criteria of biomolecules. This study represents an important contribution in the refinement of biomolecular techniques used; also, it raises new insight regarding the consistency of combining several approaches in the identification of malaria in past populations.