A detailed feasibility study on the combined use of laser-induced breakdown spectroscopy with optical coherence tomography (LIBS/OCT), aiming at a realistic depth-resolved elemental analysis of multilayer stratigraphies in paintings, is presented. Merging a high spectral resolution LIBS system with a high spatial resolution spectral OCT instrument significantly enhances the quality and accuracy of stratigraphic analysis. First, OCT mapping is employed prior to LIBS analysis in order to assist the selection of specific areas of interest on the painting surface to be examined in detail. Then, intertwined with LIBS, the OCT instrument is used as a precise profilometer for the online determination of the depth of the ablation crater formed by individual laser pulses during LIBS depth-profile analysis. This approach is novel and enables (i) the precise in-depth scaling of elemental concentration profiles, and (ii) the recognition of layer boundaries by estimating the corresponding differences in material ablation rate. Additionally, the latter is supported, within the transparency of the object, by analysis of the OCT cross-sectional views. The potential of this method is illustrated by presenting results on the detailed analysis of the structure of an historic painting on canvas performed to aid planned restoration of the artwork.