Excellent crystallinity of material films and atomic control of their surface/interface, sufficient for the realization of their optimal physical properties, are technological premises for modern functional-device applications. Bi4Ti3O12 and related compounds attract much interest as highly insulating, ferroelectric materials for use in ferroelectric random-access memories. However, it has been difficult thus far for Bi4Ti3O12 films to satisfy such requirements when formed using vapor-phase epitaxy, owing to the high volatility of Bi in a vacuum. Here, we demonstrate that flux-mediated epitaxy is one of the most promising and widely applicable concepts to overcome this inevitable problem. The key point of this process is the appropriate selection of a multi-component flux system. A combinatorial approach has led to the successful discovery of the novel flux composition of Bi-Cu-O for Bi4Ti3O12 single-crystal film growth. The perfect single-crystal nature of the stoichiometric Bi4Ti3O12 film formed has been verified through its giant grain size and electric properties, equivalent to those of bulk single crystals. This demonstration has broad implications, opening up the possibility of preparing stoichiometric single-crystal oxide films via vapor-phase epitaxy, even if volatile constituents are required.