Rural areas and peripheral borderland territories are experiencing socio-economic marginalization featuring depopulation, population aging, and an increasing inequality gap in the quality of life compared to cities. Integrated rural tourism is argued to be ideal for supporting the well-being of rural communities, providing an additional income, decreasing unemployment, offering new and appealing jobs out of traditional rural activities, while preserving the conventional lifestyle. In this study, we discovered the tourism capacity of rural borderland territories affected by cross-border tourism using the data on the geography of cross-border movements, the distribution of tourist sights, and the density of tourist accommodation facilities. The geographical scope of the study covered two cross-border coastal regions—the Russian–Polish region on the Baltic Sea and the Russian–Kazakh region on the Caspian Sea. The statistical and geoinformation analysis were used to allocate areas of prospecting rural tourism integrated with cross-border movement. The research results on the development and distribution of tourist infrastructure suggest that: the rural territories of these regions feature tourist attractions and accommodation facilities at a different level of density and remoteness from the border crossing; each cross-border region is featuring different types of travel restrictions for tourists; and both border-land territories show asymmetry by the more active Russian tourists traveling abroad. Each of the regions under consideration is attractive for cross-border tourism while having different degrees of penetration of tourist flows into the interior territories and coverage of rural areas. The study resulted in a tourist flow model that allows integrating rural areas.