Durant la première moitié du XIXe siècle, le moyen le plus rapide de relier Bordeaux à Sète était de prendre la diligence de Bordeaux à Toulouse, en 18 heures, puis d'emprunter le canal du Midi pour rejoindre Sète en 28 heures.
À cette époque, Toulouse était en retard sur la révolution industrielle, et beaucoup blâment le maire Joseph de Villèle d'avoir refusé le chemin de fer au début du siècle.
En 1853, Émile et Isaac Pereire fondent la Compagnie des Chemins de fer du Midi. Ils ouvrent trois ans plus tard la ligne ferroviaire d'Agen à Toulouse, qui fut bientôt complétée par une ligne de Bordeaux à Sète, en 1857. Pour éviter toute concurrence, la compagnie rachète même les droits d'exploitation du canal du Midi.
Le bâtiment de la gare Matabiau a été construit seulement entre 1903 et 1905, remplaçant la gare primitive : le débarcadère du chemin de fer. Le nom du quartier Matabiau vient de l'ancien marché au boeuf (Matabiau = tuer le boeuf).
Le bâtiment voyageurs que nous connaissons aujourd'hui a été dessiné par l'architecte Toulonnais Marius Toudoire, et a été réalisé en pierre de Saintonge. Les 26 principales villes desservies de Bordeaux à Sète ont chacune leur blason sur la façade.
En 1938, la Compagnie du Midi est fusionnée et nationalisée avec les quatre autres grandes compagnies de chemin de fer nationales (Nord, Est, Paris-Orléans, Paris-Lyon-Méditerranée) pour former la SNCF.
Le bâtiment a fait l'objet d'un remaniement en 1983, juste avant d'être déclaré monument historique.
Depuis 1990, elle reçoit les TGV en provenance de la LGV Atlantique, ramenant Toulouse à 5h à 5h30 de Paris, au lieu de 6h à 7h par la ligne historique passant par Orléans et Limoges.
En 2004, la gare est devenue le terminus nord de la ligne D, une ligne TER Midi-Pyrénées cadencée vers Muret mise en place en collaboration avec Tisséo, la régie des transports en commun toulousains.
Le 7 décembre 2009, un sixième quai a été inauguré, accueillant deux nouvelles voies : les voies 10 et 11. Cette réalisation entend répondre à la saturation de la gare en permettant d'améliorer le service et d'augmenter le nombre de trains (jusqu'à cinquante de plus par jour).
En 2009 elle est fréquentée par 9 millions de voyageurs annuels.
La gare permet de nombreuses correspondances : avec le réseau urbain de Toulouse, Tisséo (métro et bus), avec le réseau interurbain départemental, Arc-en-Ciel, et régional (TER Midi-Pyrénées). Au nord du bâtiment voyageurs se trouve également un parking payant.