An information-based optimal sensor placement (OSP) strategy is explored in the context of bridge health monitoring. An inversed greedy algorithm is proposed for optimizing the sensor placement since the conventional greedy algorithm can only achieve a near-optimal solution with large uncertainty. This study intends to reconstruct complete modal shape configuration based on the deployed sensors by employing Gaussian process regression (GPR) method, where the modal components from the deployed sensors are utilized for searching the optimal positions on the bridge. First of all, the GPR method is exploited to establish a probability model of the unsensed positions based on the data from the deployed sensors. Then, to maximize the information that the probability model contains, the mutual information is employed as the objective function and interpreted by the proposed inversed greedy algorithm. The performance of the proposed method is verified through a numerical case study, where the conventional greedy algorithm and the genetic algorithm are also implemented for the purpose of comparison with the proposed algorithm. The results show that the inversed greedy algorithm outperforms the greedy algorithm and the genetic algorithm since it can provide a solution which is closer to the optimum in terms of the prediction error.