A common approach for the development of partitioned schemes employing different time integrators on different subdomains is to lag the coupling terms in time. This can lead to accuracy issues, especially in multistage methods. We present a novel framework for partitioned heterogeneous time-integration methods, which allows the coupling of arbitrary multistage and multistep methods without reducing their order of accuracy. At the core of our approach are accurate estimates of the interface flux obtained from the Schur complement of an auxiliary monolithic system. We use these estimates to construct a polynomial-in-time approximation of the interface flux over the current time coupling window. This approximation provides the interface boundary conditions necessary to decouple the subdomain problems at any point within the coupling window. In so doing, our framework enables a flexible choice of time-integrators for the individual subproblems without compromising the time-accuracy at the coupled problem level. This feature is the main distinction between our framework and other approaches. To demonstrate the framework, we construct a family of partitioned heterogeneous time-integration methods, combining multistage and multistep methods, for a simplified tracer transport component of the coupled air-sea system in Earth System Models. We present numerical tests evaluating accuracy and flux conservation for different pairs of time-integrators from the explicit Runge-Kutta and Adams-Moulton families.