We develop the Fredholm theory for Toeplitz operators, with symbols in the C*-algebra $D = [SO, SAP]_{n, n}$ generated by all slowly oscillating (SO) and semi-almost periodic (SAP) $n\times n$ matrix functions, on the Hardy spaces $H^p_n$ (with $1 < p < \infty$) over the upper half-plane. Using limit operator techniques, we get necessary Fredholm conditions for any operator in the Banach algebra ${\rm alg}(S, D)$ of singular integral operators with coefficients in $D$ on the space $[L^p (\mathbb{R})]_n$. Applying the Allan–Douglas local principle and the theory of Toeplitz operators with SAP matrix symbols, we also establish Fredholm criteria for Toeplitz operators with matrix symbols $g \in D$ on the space $H^p_n$. An index formula for Fredholm Toeplitz operators with matrix symbols in $D$ is obtained on the basis of an appropriate approximation of slowly oscillating components of the symbols.