The extension of multiple-input multiple-output (MIMO) sphere decoding from the narrowband case to wideband systems based on orthogonal frequency division multiplexing (OFDM) requires the computation of a QR decomposition for each of the data-carrying OFDM tones. Since the number of data-carrying tones ranges from 48 (as in the IEEE 802.11 a/g, standards) to 6817 (as in the DVBT standard), the corresponding computational complexity will in general be significant. This paper presents two algorithms for interpolation-based QR decomposition in MIMO-OFDM systems. An in-depth computational complexity analysis shows that the proposed algorithms, for a sufficiently high number of data-carrying tones and small channel order, exhibit significantly smaller complexity than brute-force per-tone QR decomposition.