Aims. The propagation of magnetohydrodynamic (MHD) waves in a finite, compressible magnetic flux tube with an elliptical cross-section embedded in a magnetic environment is investigated. Methods. We present the derivation of the general dispersion relation of linear magneto-acoustic wave propagation for a compressible magnetic flux tube with elliptical cross-section in a plasma with finite beta. The wave modes of propagation for the n=0 (symmetric) sausage and n=1 (anti-symmetric) kink oscillations are then examined within the limit of the thin flux tube approximation. Results. It is shown that a compressible magnetic tube with elliptical cross-section supports slow and fast magneto-acoustic waves. In the thin tube approximation, the slow sausage mode and the slow and fast kink modes are found in analogue to a circular cross-section. However, the kink modes propagate with different phase speeds depending on whether the axial displacement takes place along the major or minor axis of the ellipse. This feature is present in both the slow and the fast bands, providing two infinite sets of slow kink modes and two infinite sets of fast kink modes, i.e. each corresponding cylindrical mode splits into two sets of modes due to the ellipticity. The difference between the phase speeds along the different axis is dependent on the ratio of the lengths of the two axes. Analytical expressions for the phase speeds are found. We show that the sausage modes do not split due to the introduced ellipticity and only the phase speed is modified when compared to the appropriate cylindrical counterpart. The percentage difference between the periods of the circular and elliptical cross-sections is also calculated, which reaches up to for oscillations along the major axis. The level of difference in period could be very important in magneto-seismological applications, when observed periods are inverted into diagnostic properties (e.g. magnetic field strength, gravitational scale height, tube expansion parameter). Also shown is the perturbation of focal points of the elliptical cross-section for different modes. It is found that the focal points are unperturbed for the sausage mode, but are perturbed for all higher modes.