This paper has four main results: (i) it shows that left-invariant geodesic flows on a broad class of two-step nilmanifolds—which are dubbed almost non-singular—are integrable in the non-commutative sense of Nehoros˘ev; (ii) the left-invariant geodesic flows on all Heisenberg–Reiter nilmanifolds are Liouville integrable; (iii) the topological entropy of a left-invariant geodesic flow on a two-step nilmanifold vanishes; (iv) there exist two-step nilmanifolds with non-integrable left-invariant geodesic flows. It is also shown that for each of the integrable Hamiltonians investigated here, there is a C^2-open neighbourhood in C^2(T^* M) such that every integrable Hamiltonian vector field in this neighbourhood must have wild first integrals.