This paper proposes computationally efficient methods for identifying Koopman operators using multi-step output-error minimization. The two complementary approaches proposed in the paper trade-off between model accuracy and computational efficiency. Then, we provide an extensive comparison of the proposed methods to the standard Extended Dynamic Mode Decomposition (EDMD) approach through numerical examples. The results demonstrate the advantages of the proposed methods in terms of open and closed-loop performance, while remaining computationally efficient.