Mit dem Radsport begann Włoszczowska in Karpacz, ihr Trainer war Zdzisław Szmit. Ihre ersten internationalen Erfolge hatte Maja Włoszczowska als Juniorin: in den Jahren 2000 und 2001 jeweils mit dem zweiten Platz bei den UCI-Mountainbike-Weltmeisterschaften im Cross Country (olympisch) XCO sowie dem dritten Platz bei den UCI-Straßen-Weltmeisterschaften 2001 im Straßenrennen. 2002 begann sie ein Finanzmathematikstudium an der Technischen Universität Breslau (Politechnika Wrocławska) im Fachbereich für Grundlegende Probleme der Technik. Kurze Zeit darauf wurde sie Mitglied des polnischen Lotto-Teams, studierte aber weiterhin und schloss ihr Studium nach fünfeinhalb Jahren ab.
2003 wurde Włoszczowska im Alter von 20 Jahren die erste Weltmeisterin im Mountainbike-Marathon XCM überhaupt. Im Jahr 2004 gewann sie die ersten Medaillen bei Welt- und Europameisterschaften im XCO. Bis 2021 gewann sie insgesamt neun Medaillen bei Weltmeisterschaften, darunter die Goldmedaille im XCO im Jahr 2010, und auch neun Medaillen bei Europameisterschaften, darunter die Goldmedaille im XCO im Jahr 2009. Im Jahr 2004 wurde sie auch erstmals nationale Meisterin im XCO, es folgten insgesamt 17 nationale Titel, zuletzt in der Saison 2021 im XCO, XCM und im Short Track XCC.
Neben dem Mountainbikesport war Włoszczowska gelegentlich auch auf der Straße aktiv, unter anderem gewann sie in den Jahren 2006 und 2007 drei nationale Titel auf der Straße.
Ihren ersten UCI-Mountainbike-Weltcup-Erfolg erzielte Włoszczowska in der Saison 2008, es folgten zwei Siege in den Jahren 2010 und 2012. Die beste Platzierung in der Weltcup-Gesamtwertung hatte sie in der Saison 2017 mit Platz zwei. Im Juli 2018 holte sich die damals 34-jährige Polin im Val di Sole (Italien) nach sechs Jahren ihren vierten Weltcupsieg vor der Kanadierin Emily Batty und der Schweizerin Jolanda Neff.[2]
Nachdem Włoszczowska bei den Weltmeisterschaften 2021 als Vierte das Podest noch knapp verpasst hatte, gewann sie beim letzten Rennen ihrer Karriere noch einmal die WM-Silbermedaille im MTB-Marathon.[3]