Background: Mosquitoes are vectors of many serious pathogens in tropical and sub-tropical countries. Current control strategies almost entirely rely upon insecticides, which increasingly face the problems of high cost, increasing mosquito resistance and negative effects on non-target organisms. Alternative strategies include the proposed use of inherited life-shortening agents, such as the Wolbachia bacterium. By shortening mosquito vector lifespan, Wolbachia could potentially reduce the vectorial capacity of mosquito populations. We have recently been able to stably transinfect Aedes aegypti mosquitoes with the life-shortening Wolbachia strain wMelPop, and are assessing various aspects of its interaction with the mosquito host to determine its likely impact on pathogen transmission as well as its potential ability to invade A. aegypti populations. Methodology/Principal Findings: Here we have examined the probing behavior of Wolbachia-infected mosquitoes in an attempt to understand both the broader impact of Wolbachia infection on mosquito biology and, in particular, vectorial capacity. The probing behavior of wMelPop-infected mosquitoes at four adult ages was examined and compared to uninfected controls during video-recorded feeding trials on a human hand. Wolbachia-positive insects, from 15 days of age, showed a drastic increase in the time spent pre-probing and probing relative to uninfected controls. Two other important features for blood feeding, saliva volume and apyrase content of saliva, were also studied. Conclusions/Significance: As A. aegypti infected with wMelPop age, they show increasing difficulty in completing the process of blood feeding effectively and efficiently. Wolbachia-infected mosquitoes on average produced smaller volumes of saliva that still contained the same amount of apyrase activity as uninfected mosquitoes. These effects on blood feeding behavior may reduce vectorial capacity and point to underlying physiological changes in Wolbachia-infected mosquitoes.