Damage caused in bridges can be hidden by the service conditions mainly due to environment effects as temperature and traffic loading. The literature review indicates that the majority of investigations are limited since they do not consider these effects or they are applied under laboratory conditions and not to real bridges. The temperature effects on the natural frequencies of bridges have shown to be non-linear. In this context, this article presents a damage detection strategy considering a more robust kernel-based method (KPCA) which is the nonlinear extension of the principal component analysis (PCA) to take into account the environmental conditions of the bridge such as the non-linearity of the temperature effects in the natural frequencies. This method is combined with a clustering analysis in order to group the data with similar features both for undamaged and damaged conditions, and in this way the structural damages can be identified. The main contribution is a novel damage detection methodology based on advance statistical and machine learning algorithms to account for the non-linear environmental effects. The method is checked using measurements from the Z24 bridge, which was subjected to progressive structural damages while monitored for almost a year. The results show good performance of the proposed algorithm and highly reducing the computational cost.