This article aims at proposing various estimates of the size of the Representative Volume Element (RVE) of random linear elastic matrix–inclusion composites. These estimates are derived from the computation of the apparent behavior of finite size volume elements (VE) by a new procedure presented in [[18]] by Salmi et al. (2012) and briefly recalled. Two different points of view to define an RVE are considered: the RVE is defined as being the smallest VE required either to evaluate numerically the considered effective property of the composite by appropriate statistical averaging of apparent ones, or to be allowed to replace any instance of the heterogeneous material by a unique homogeneous equivalent one in structural mechanics problems. In order to introduce the fluctuations of the apparent properties within such definitions of the RVE size, we first study the statistics of the apparent properties. Then, relying on the results of this statistical study, several proposals of RVE criteria are presented and applied to random linear elastic fiber–matrix composites for several contrasts and inclusion (or pore) volume fractions.