Aldana, deren Vater Marcos Aldana als Saxophonist 1991 Semi-Finalist in der Thelonious Monk International Jazz Saxophone Competition wurde, lernte ab dem Alter von sechs Jahren bei ihrem Vater Altsaxophon. Unter dem Einfluss von Sonny Rollins wechselte sie später aufs Tenorinstrument. Bereits im Alter von 16 Jahren spielte sie mit eigenen Bands in den wichtigen Jazzclubs von Chiles Hauptstadt. 2005 lud Danilo Pérez sie ein, auf dem Panama Jazz Festival zu spielen. 2006 kam sie in die Vereinigten Staaten, wo sie am Berklee College of Music studierte.
Nach Beendigung ihres Studiums 2009 zog sie nach New York City, wo George Coleman ihr Mentor wurde und sie im Blue Note, im Smalls und im Lincoln Center auftrat. Nachdem sie 2010 ihr erstes Album Free Fall für Greg Osbys Label Inner Circle Music aufnahm, folgte 2012 Second Cycle und 2014 Melissa Aldana & Crash Trio (auf Concord, mit Pablo Menares, Bass, und Francisco Mela, Schlagzeug). Ein weiteres Album mit dem Crash Trio, Back Home, erschien 2016, wobei Jochen Rückert Mela am Schlagzeug ablöste.[1] 2019 erschien auf Motéma Music ihr Quintettalbum Visions, das durch Gemälde von Frida Kahlo und ihre lateinamerikanischen Wurzeln inspiriert ist; auf ihm arbeitete sie mit Sam Harris, Pablo Menares, Tommy Crane und Joel Ross.[2]
Aldana gewann 2013 die Thelonious Monk International Jazz Saxophone Competition. Weiterhin wurde sie mit dem nationalen Kunstpreis Altazor in Chile für das beste Album und mit dem Lincoln Center Martin E. Segal Award ausgezeichnet.[5] 2015 gewann sie in den Down Beat Kritiker-Polls in der Rising Star Kategorie. 2019 erhielt sie für „Elsewhere“ (auf ihrem Album Visions, 2019) ihre erste Grammy-Nominierung in der Kategorie Bestes improvisiertes Jazzsolo.[6]