Rigidity percolation (RP) occurs when mechanical stability emerges in disordered networks as constraints or components are added. Here we discuss RP with structural correlations, an effect ignored in classical theories albeit relevant to many liquid-to-amorphous-solid transitions, such as colloidal gelation, which are due to attractive interactions and aggregation. Using a lattice model, we show that structural correlations shift RP to lower volume fractions. Through molecular dynamics simulations, we show that increasing attraction in colloidal gelation increases structural correlation and thus lowers the RP transition, agreeing with experiments. Hence, the emergence of rigidity at colloidal gelation can be understood as a RP transition, but occurs at volume fractions far below values predicted by the classical RP, due to attractive interactions which induce structural correlation.