A novel second-order computational homogenization scheme suitable for the multi- scale modelling of macroscopic localization and size effects is proposed. The second-order scheme is an extension of the classical computational homogenization framework and is based on a proper incorporation of the gradient of the macroscopic deformation gradient tensor into the kinematical macro-micro scale transition. From the microstructural analysis the macroscopic stress and higher-order stress tensors are obtained, thus delivering a microstructurally based constitutive response of the macroscopic second gradient continuum. As an example the approach is applied for the multi-scale analysis of macroscopic localization in a microstructurally perforated plate and simple shear of a constrained heterogeneous strip, where a pronounced boundary size effect appears. The distinct role of the size of a representative volume element, which in the second-order computational homogenization framework is related to the length scale of the macroscopic homogenized continuum, is discussed.