This paper proposes a novel multi-scale approach for the reliability analysis of composite structures that accounts for both microscopic and macroscopic uncertainties, such as constituent material properties and ply angle. The stochastic structural responses, which establish the relationship between structural responses and random variables, are achieved using a stochastic multi-scale finite element method, which integrates computational homogenisation with the stochastic finite element method. This is further combined with the first- and second-order reliability methods to create a unique reliability analysis framework. To assess this approach, the deterministic computational homogenisation method is combined with the Monte Carlo method as an alternative reliability method. Numerical examples are used to demonstrate the capability of the proposed method in measuring the safety of composite structures. The paper shows that it provides estimates very close to those from Monte Carlo method, but is significantly more efficient in terms of computational time. It is advocated that this new method can be a fundamental element in the development of stochastic multi-scale design methods for composite structures.